FZU2273-Triangles

Triangles

This is a simple problem. Given two triangles A and B, you should determine they are intersect, contain or disjoint. (Public edge or point are treated as intersect.)

Input
First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: X1 Y1 X2 Y2 X3 Y3 X4 Y4 X5 Y5 X6 Y6. All the coordinate are integer. (X1,Y1) , (X2,Y2), (X3,Y3) forms triangles A ; (X4,Y4) , (X5,Y5), (X6,Y6) forms triangles B.

-10000<=All the coordinate <=10000

Output
For each test case, output “intersect”, “contain” or “disjoint”.

Sample Input
2
0 0 0 1 1 0 10 10 9 9 9 10
0 0 1 1 1 0 0 0 1 1 0 1
Sample Output
disjoint
intersect

题目大意：判断两个三角形是否相交，相离或包含
解题思路：计算几何，用判断线段相交和点在多边形内的模板。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
#define Sgn(x) (((x)<0)?(-1):(1))
#define eps 1e-8
#define INF 1e10
#define Pi (acos(-1.0))
double Deg2Rad(double deg) {return (deg*Pi/180.0);}
double Rad2Deg(double rad) {return (rad*180.0/Pi);}
double Sin(double deg) {return sin(Deg2Rad(deg));}
double Cos(double deg) {return cos(Deg2Rad(deg));}
double ArcSin(double val) {return Rad2Deg(asin(val));}
double ArcCos(double val) {return Rad2Deg(acos(val));}

//点
struct POINT
{
    double x,y;
    POINT():x(0),y(0){}
    POINT(double _x,double _y):x(_x),y(_y){};
};

//两个点的距离
double Distance(const POINT &a,const POINT &b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

//线段
struct SEG
{
    POINT a;//起点
    POINT b;//终点
    SEG(){};
    SEG(POINT _a,POINT _b):a(_a),b(_b){};
};

//有公共端点o叉乘，并判拐，若正p0->p1->p2拐向左
double Cross(const POINT &a,const POINT &b,const POINT &o)
{
    return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}

//判等（值，点，直线）
bool IsEqual(double a,double b)
{
    return (abs(a-b)<eps);
}

bool IsEqual(const POINT &a,const POINT &b)
{
    return (IsEqual(a.x,b.x)&&IsEqual(a.y,b.y));
}

//判断点是否在线段上
bool IsOnSeg(const SEG &seg,const POINT &p)
{
    return (IsEqual(p,seg.a)||IsEqual(p,seg.b))||
           (((p.x-seg.a.x)*(p.x-seg.b.x)<0||
             (p.y-seg.a.y)*(p.y-seg.b.y)<0)&&
             (IsEqual(Cross(seg.b,p,seg.a),0)));
}

//判断两条线段是否相交，端点重合算相交
bool IsIntersect(const SEG &u,const SEG &v)
{
    return (Cross(v.a,u.b,u.a)*Cross(u.b,v.b,u.a)>=0)&&
           (Cross(u.a,v.b,v.a)*Cross(v.b,u.b,v.a)>=0)&&
           (max(u.a.x,u.b.x)>=min(v.a.x,v.b.x))&&
           (max(v.a.x,v.b.x)>=min(u.a.x,u.b.x))&&
           (max(u.a.y,u.b.y)>=min(v.a.y,v.b.y))&&
           (max(v.a.y,v.b.y)>=min(u.a.y,u.b.y));
}

//多边形，逆时针或顺时针给出x,y
struct POLY
{
    int n;//n个点
    double *x;
    double *y;//x,y为点的指针，首尾必须重合
    POLY():n(0),x(NULL),y(NULL){};
    POLY(int _n,const double *_x,const double *_y)
    {
        n=_n;
        x=new double[n+1];
        memcpy(x,_x,n*sizeof(double));
        x[n]=_x[0];
        y=new double[n+1];
        memcpy(y,_y,n*sizeof(double));
        y[n]=_y[0];
    }
};

//多边形顶点
POINT Vertex(const POLY &poly,int idx)
{
    idx%=poly.n;
    return POINT(poly.x[idx],poly.y[idx]);
}

//多边形的边
SEG Edge(const POLY &poly,int idx)
{
    idx%=poly.n;
    return SEG(POINT(poly.x[idx],poly.y[idx]),
               POINT(poly.x[idx+1],poly.y[idx+1]));
}

//多边形的周长
double Perimeter(const POLY &poly)
{
    double p=0.0;
    for(int i=0;i<poly.n;i++)
        p=p+Distance(Vertex(poly,i),Vertex(poly,i+1));
    return p;
}

//求多边形面积
double Area(const POLY& poly)
{
    if(poly.n<3) return double(0);
    double s=poly.y[0]*(poly.x[poly.n-1]-poly.x[1]);
    for(int i=1;i<poly.n;i++)
    {
        s+=poly.y[i]*(poly.x[i-1]-poly.x[(i+1)%poly.n]);
    }
    return s/2;
}

//多边形的重心
POINT InCenter(const POLY& poly)
{
    double S,Si,Ax,Ay;
    POINT p;
    Si=(poly.x[poly.n-1]*poly.y[0]-poly.x[0]*poly.y[poly.n-1]);
    S=Si;
    Ax=Si*(poly.x[0]+poly.x[poly.n-1]);
    Ay=Si*(poly.y[0]+poly.y[poly.n-1]);
    for(int i=1;i<poly.n;i++)
    {
        Si=(poly.x[i-1]*poly.y[i]-poly.x[i]*poly.y[i-1]);
        Ax+=Si*(poly.x[i-1]+poly.x[i]);
        Ay+=Si*(poly.y[i-1]+poly.y[i]);
        S+=Si;
    }
    S=S*3;
    return POINT(Ax/S,Ay/S);
}

//判断点是否在多边形上
bool IsOnPoly(const POLY &poly,const POINT &p)
{
    for(int i=0;i<poly.n;i++)
    {
        if(IsOnSeg(Edge(poly,i),p))
        {
            return true;
        }
    }
    return false;
}

//判断点是否在多边形内部
bool IsInPoly(const POLY &poly,const POINT &p)
{
    SEG L(p,POINT(INF,p.y));
    int cnt=0;
    for(int i=0;i<poly.n;i++)
    {
        SEG S=Edge(poly,i);
        if(IsOnSeg(S,p)) return true;
        if(!IsEqual(S.a.y,S.b.y))
        {
            POINT &q=(S.a.y>S.b.y)?(S.a):(S.b);
            if(IsOnSeg(L,q)) ++cnt;
            else if(!IsOnSeg(L,S.a)&&!IsOnSeg(L,S.b)&&IsIntersect(S,L)) ++cnt;
        }
    }
    return (cnt%2!=0);
}

//判断是否为简单多边形
bool IsSimple(const POLY& poly)
{
    if(poly.n<3) return false;
    SEG L1,L2;
    for(int i=0;i<poly.n-1;i++)
    {
        L1=Edge(poly,i);
        for(int j=i+1;j<poly.n;j++)
        {
            L2=Edge(poly,j);
            if(j==i+1)
            {
                if(IsOnSeg(L1,L2.b)||IsOnSeg(L2,L1.a)) return false;
            }else if(j==poly.n-i-1)
            {
                if(IsOnSeg(L1,L2.a)||IsOnSeg(L2,L1.b)) return false;
            }else
            {
                if(IsIntersect(L1,L2)) return false;
            }
        }
    }
    return true;
}

//点阵的凸包，返回一个多边形
POLY ConvexHull(const POINT *s,int n)//不适用于点少于3个的情况
{
    POINT *points=new POINT[n];
    memcpy(points,s,n*sizeof(POINT));
    double *X=new double[n];
    double *Y=new double[n];
    int i,j,k=0,top=2;
    for(int i=1;i<n;i++)
    {
        if((points[i].y)<points[k].y||
          ((points[i].y==points[k].y)&&
           (points[i].x<points[k].x)))
        {
            k=i;
        }
    }
    swap(points[0],points[k]);
    for(i=1;i<n-1;i++)
    {
        k=i;
        for(j=i+1;j<n;j++)
        {
            if((Cross(points[j],points[k],points[0])>0)||
              ((Cross(points[j],points[k],points[0])==0)&&
               (Distance(points[0],points[j])<Distance(points[0],points[k]))))
            {
                k=j;
            }
        }
        swap(points[i],points[k]);
    }
    X[0]=points[0].x;Y[0]=points[0].y;
    X[1]=points[1].x;Y[1]=points[1].y;
    X[2]=points[2].x;Y[2]=points[2].y;
    for(i=3;i<n;i++)
    {
        while(Cross(points[i],POINT(X[top],Y[top]),
              POINT(X[top-1],Y[top-1]))>=0)
        {
            top--;
        }
        ++top;
        X[top]=points[i].x;
        Y[top]=points[i].y;
    }
    delete[] points;
    POLY poly(++top,X,Y);
    delete[] X;
    delete[] Y;
    return poly;
}

double xa[5],ya[5],xb[5],yb[5];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        for(int i=0;i<3;i++)
        {
            scanf("%lf%lf",&xa[i],&ya[i]);
        }
        for(int i=0;i<3;i++)
        {
            scanf("%lf%lf",&xb[i],&yb[i]);
        }
        POLY polya=POLY(3,xa,ya);
        POLY polyb=POLY(3,xb,yb);
        bool inter=false;
        for(int i=1;i<=3;i++)
        {
            SEG sa=Edge(polya,i);
            for(int j=1;j<=3;j++)
            {
                SEG tmp=Edge(polyb,j);
                if(IsIntersect(sa,tmp)) inter=true;
            }
        }
        if(inter) {printf("intersect\n");continue;}
        POINT pa1=Vertex(polya,1);
        POINT pb1=Vertex(polyb,1);
        bool cont=false;
        if(IsInPoly(polyb,pa1)||IsInPoly(polya,pb1)) cont=true;
        if(cont) {printf("contain\n");continue;}
        printf("disjoint\n");
    }
    return 0;
}