POJ 1279&1474(多角形のコア)

多角形の核について、私のこのブログで紹介されているので、あまり言わないで、差は多くないのはテンプレートにくっついているのではないでしょうか.POJ 1279多角形の核の面積を求めます(G++コンパイラが問題があるようで、C++は過ぎました)

#include
#include
#include
#define MAXN 1550
using namespace std;
struct poi
{
    double x,y;
    poi(double x = 0,double y = 0) :x(x),y(y) {}    
};
typedef poi vec;
vec operator +(vec A,vec B) {return vec(A.x+B.x, A.y+B.y);}
vec operator -(vec A,vec B) {return vec(A.x-B.x, A.y-B.y);}
vec operator *(vec A,double p) {return vec(A.x*p, A.y*p);}
const double eps = 1e-6;
int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    else return x>0?1:-1;
}
double cross(vec A,vec B) {return A.x*B.y - A.y*B.x;}
double dot(vec A,vec B) {return A.x*B.x + A.y*B.y;}
poi GetLineIntersection(poi A,vec v,poi B,vec w)
{
    double t = cross(w, A-B) /cross(v,w);
    return A + v*t;
}
bool OnSegment(poi p,poi A,poi B)
{
    //return dcmp(cross(A-p,B-p)) == 0&&dcmp(dot(A-p,B-p)) < 0;
    double mnx = min(A.x, B.x), mxx = max(A.x, B.x);
    double mny = min(A.y, B.y), mxy = max(A.y, B.y);
    return (mnx <= p.x + eps && p.x - eps <= mxx) && (mny <= p.y + eps && p.y - eps <= mxy);
}
struct polygon{
    poi a[MAXN];
    int sz;
};
polygon CutPolygon(polygon poly, poi A, poi B)
{
    polygon newpoly;
    int m = 0,n = poly.sz;
    for(int i = 0; i < n; i++)
    {
        poi C = poly.a[i], D = poly.a[(i+1)%n];
        if(dcmp(cross(B-A, C-A)) <= 0) newpoly.a[m++] = C;
        if(dcmp(cross(B-A, C-D)) != 0) {
            poi ip = GetLineIntersection(A, B-A, C, D-C);
            if(OnSegment(ip, C, D)) newpoly.a[m++] = ip;
        }
    }
    newpoly.sz = m;
    return newpoly;
}
double Get_Kernel(polygon poly)
{
    polygon knl;
    //knl.a[0] = poi(-1e6,-1e6),knl.a[1] = poi(1e6,-1e6),knl.a[2] = poi(1e6,1e6),knl.a[3] = poi(-1e6,1e6);
    knl.a[0] = poi(-1e6,-1e6),knl.a[1] = poi(-1e6,1e6),knl.a[2] = poi(1e6,1e6),knl.a[3] = poi(1e6,-1e6);//        
    knl.sz = 4;
    for(int i = 0; i < poly.sz; i++)
    {
        poi A = poly.a[i], B = poly.a[(i+1)%poly.sz];
        knl = CutPolygon(knl,A,B);
    }
    double area = 0;
    for(int i = 1; i < knl.sz-1; i++)
        area += cross(knl.a[i]-knl.a[0], knl.a[i+1]-knl.a[0]);
    return area;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        polygon poly;
        poly.sz = n;
        for(int i = 0; i < n; i++) scanf("%lf%lf",&poly.a[i].x,&poly.a[i].y);
        printf("%.2lf
",fabs(Get_Kernel(poly))/2);
    }
}

POJ 1474多角形の核が存在するかどうかを求めて、毎回切断して残りの点数を求めます

/*
       ，    
*/
#include
#include
#include
#define MAXN 110
using namespace std;
const double eps = 1e-6;
struct poi
{
    double x,y;
    poi(double x = 0,double y = 0) :x(x),y(y) {}
}pos[MAXN];
typedef poi vec;
vec operator +(vec A,vec B) {return vec(A.x + B.x, A.y + B.y);}
vec operator -(vec A,vec B) {return vec(A.x - B.x, A.y - B.y);}
vec operator *(vec A,double p) {return vec(A.x*p, A.y*p);}
int dcmp(double x)//   bool
{
    if(fabs(x) < eps) return 0;
    else return x>0?1:-1;
}
double cross(vec A,vec B) {return A.x*B.y - A.y*B.x;}
double dot(vec A,vec B) {return A.x*B.x + A.y*B.y;}
poi GetLineIntersection(poi A,vec v,poi B,vec w)
{
    double t = cross(w,A - B) /cross(v,w);
    return A + v*t;
}
bool OnSegment(poi p,poi A,poi B) 
{
    //return dcmp(cross(A-p,B-p)) == 0&&dcmp(dot(A-p,B-p)) < 0;            
    double mnx = min(A.x, B.x), mxx = max(A.x, B.x);
    double mny = min(A.y, B.y), mxy = max(A.y, B.y);
    return (mnx <= p.x + eps && p.x - eps <= mxx) && (mny <= p.y + eps && p.y - eps <= mxy);
}
struct polygon{
    poi a[MAXN];
    int sz;
};
polygon CutPolygon(polygon poly, poi A, poi B)
{
    int m = 0,n = poly.sz;
    polygon newpoly;
    for(int i = 0; i < n; i++)
    {
        poi C = poly.a[i], D = poly.a[(i+1)%n];
        if(dcmp(cross(B - A, C - A)) <= 0) newpoly.a[m++] = C;//f**kf**kf**kf**kf**k,          ,   <=
        if(dcmp(cross(B - A, C - D)) != 0){
            poi ip = GetLineIntersection(A, B-A, C, D-C);
            if(OnSegment(ip, C, D)) newpoly.a[m++] = ip;
        }
    }
    newpoly.sz = m;
    return newpoly;
}
bool has_kernel(polygon poly)
{
    polygon knl;
    knl.a[0] = poi(-1e6,-1e6),knl.a[1] = poi(1e6,-1e6),knl.a[2] = poi(1e6,1e6),knl.a[3] = poi(-1e6,1e6);//      WA
    knl.sz = 4;
    for(int i = 0; i < poly.sz; i++)
    {
        poi A = poly.a[i], B = poly.a[(i+1)%poly.sz];
        knl = CutPolygon(knl,A,B);
        if(knl.sz == 0) return false;
    }
    return true;
}
int main()
{
    polygon poly;
    int cas = 0,n;
    while(scanf("%d",&n) != EOF&&n)
    {
        for(int i = 0; i < n; i++) scanf("%lf%lf",&poly.a[i].x,&poly.a[i].y);
        poly.sz = n;
        printf("Floor #%d
",++cas);
        if(has_kernel(poly)) printf("Surveillance is possible.

");
        else printf("Surveillance is impossible.

");
    }
}