FZU 2273 Triangles 第八届福建省赛（三角形面积交有重边算相交）

Problem Description

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

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

观察样例可以发现，如果边有重叠部分，此题也算相交。

因此我套用多边形面积交的模板http://www.cnblogs.com/Annetree/p/6535294.html

如果有重合面积，有两种情况：包含或相交，特殊判断包含即可

如果没有重合面积，也有两种情况：相交（线）和相离，特殊判断线部分重合即可

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<cstdlib>
  7 #include<queue>
  8 #include<map>
  9 #include<stack>
 10 #include<set>
 11 
 12 using namespace std;
 13 
 14 const int maxn=555;
 15 const int maxisn=10;
 16 const double eps=1e-8;
 17 const double pi=acos(-1.0);
 18 
 19 int dcmp(double x){
 20     if(x>eps) return 1;
 21     return x<-eps ? -1 : 0;
 22 }
 23 inline double Sqr(double x){
 24     return x*x;
 25 }
 26 
 27 #define zero(x)(((x)>0?(x):-(x))<eps)
 28 struct Point{
 29     double x,y;
 30     Point(){x=y=0;}
 31     Point(double x,double y):x(x),y(y){};
 32     friend Point operator + (const Point &a,const Point &b) {
 33         return Point(a.x+b.x,a.y+b.y);
 34     }
 35     friend Point operator - (const Point &a,const Point &b) {
 36         return Point(a.x-b.x,a.y-b.y);
 37     }
 38     friend bool operator == (const Point &a,const Point &b) {
 39         return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
 40     }
 41     friend Point operator * (const Point &a,const double &b) {
 42         return Point(a.x*b,a.y*b);
 43     }
 44     friend Point operator * (const double &a,const Point &b) {
 45         return Point(a*b.x,a*b.y);
 46     }
 47     friend Point operator / (const Point &a,const double &b) {
 48         return Point(a.x/b,a.y/b);
 49     }
 50     friend bool operator < (const Point &a, const Point &b) {
 51         return a.x < b.x || (a.x == b.x && a.y < b.y);
 52     }
 53     inline double dot(const Point &b)const{
 54         return x*b.x+y*b.y;
 55     }
 56     inline double cross(const Point &b,const Point &c)const{
 57         return (b.x-x)*(c.y-y)-(c.x-x)*(b.y-y);
 58     }
 59 
 60 };
 61 
 62 Point LineCross(const Point &a,const Point &b,const Point &c,const Point &d){
 63     double u=a.cross(b,c),v=b.cross(a,d);
 64     return Point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v));
 65 }
 66 double PolygonArea(Point p[],int n){
 67      if(n<3) return 0.0;
 68      double s=p[0].y*(p[n-1].x-p[1].x);
 69      p[n]=p[0];
 70      for(int i=1;i<n;i++){
 71         s+=p[i].y*(p[i-1].x-p[i+1].x);
 72      }
 73      return fabs(s*0.5);
 74 }
 75 double CPIA(Point a[],Point b[],int na,int nb){
 76     Point p[maxisn],temp[maxisn];
 77     int i,j,tn,sflag,eflag;
 78     a[na]=a[0],b[nb]=b[0];
 79     memcpy(p,b,sizeof(Point)*(nb+1));
 80     for(i=0;i<na&&nb>2;++i){
 81         sflag=dcmp(a[i].cross(a[i+1],p[0]));
 82         for(j=tn=0;j<nb;++j,sflag=eflag){
 83             if(sflag>=0) temp[tn++]=p[j];
 84             eflag=dcmp(a[i].cross(a[i+1],p[j+1]));
 85             if((sflag^eflag)==-2)
 86                 temp[tn++]=LineCross(a[i],a[i+1],p[j],p[j+1]);
 87         }
 88         memcpy(p,temp,sizeof(Point)*tn);
 89         nb=tn,p[nb]=p[0];
 90     }
 91     if(nb<3) return 0.0;
 92     return PolygonArea(p,nb);
 93 }
 94 double SPIA(Point a[],Point b[],int na,int nb){
 95     int i,j;
 96     Point t1[4],t2[4];
 97     double res=0.0,if_clock_t1,if_clock_t2;
 98     a[na]=t1[0]=a[0];
 99     b[nb]=t2[0]=b[0];
100     for(i=2;i<na;i++){
101         t1[1]=a[i-1],t1[2]=a[i];
102         if_clock_t1=dcmp(t1[0].cross(t1[1],t1[2]));
103         if(if_clock_t1<0) swap(t1[1],t1[2]);
104         for(j=2;j<nb;j++){
105             t2[1]=b[j-1],t2[2]=b[j];
106             if_clock_t2=dcmp(t2[0].cross(t2[1],t2[2]));
107             if(if_clock_t2<0) swap(t2[1],t2[2]);
108             res+=CPIA(t1,t2,3,3)*if_clock_t1*if_clock_t2;
109         }
110     }
111     return res;
112     //return PolygonArea(a,na)+PolygonArea(b,nb)-res;
113 }
114 
115 Point a[222],b[222];
116 Point aa[222],bb[222];
117 
118 double length(Point p1,Point p2)//求边长
119 {
120     double res=sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
121     return res;
122 }
123 
124 double area_triangle(double l1,double l2,double l3)//求三角形面积
125 {
126     double s=(l1+l2+l3)/2.0;
127     double res=sqrt(s*(s-l1)*(s-l2)*(s-l3));
128     return res;
129 }
130 
131 double xmult(Point p1,Point p2,Point p0)
132 {
133     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
134 }
135 
136 int parallel(Point u1,Point u2,Point v1,Point v2)//判断平行
137 {
138     return zero((u1.x-u2.x)*(v1.y-v2.y)-(v1.x-v2.x)*(u1.y-u2.y));
139 }
140 
141 int dot_online_in(Point p,Point l1,Point l2)
142 {
143     return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
144 }
145 int main()
146 {
147     int T;
148     scanf("%d",&T);
149     while(T--)
150     {
151         for(int i=0;i<3;i++) scanf("%lf %lf",&a[i].x,&a[i].y);
152         for(int i=0;i<3;i++) scanf("%lf %lf",&b[i].x,&b[i].y);
153         double area_double =fabs(SPIA(a,b,3,3));//重合面积
154         double l1=length(a[0],a[1]),l2=length(a[0],a[2]),l3=length(a[1],a[2]);
155         double l4=length(b[0],b[1]),l5=length(b[0],b[2]),l6=length(b[1],b[2]);
156         if(area_double>eps) //包含或相交
157         {
158             if(abs(area_double-area_triangle(l1,l2,l3))<eps)
159                 printf("contain
");
160             else if(abs(area_double-area_triangle(l4,l5,l6))<eps)
161                 printf("contain
");
162             else
163                 printf("intersect
");
164         }
165         else //相交或相离
166         {
167             bool flag=false;
168             //判断是否有边重合
169             for(int i=0;i<2;i++)
170             {
171                 for(int ii=i+1;ii<3;ii++)
172                 {
173                     for(int j=0;j<2;j++)
174                     {
175                         for(int jj=j+1;jj<3;jj++)
176                         {
177                             if(parallel(a[i],a[ii],b[j],b[jj]))
178                                 if(dot_online_in(a[i],b[j],b[jj]))
179                                 {
180                                     flag=true;
181                                     break;
182                                 }
183                         }
184                         if(flag)
185                             break;
186                     }
187                     if(flag)
188                         break;
189                 }
190                 if(flag)
191                     break;
192             }
193             if(flag)
194                 printf("intersect
");
195             else
196                 printf("disjoint
");
197                                                
198         }
199     }
200     return 0;
201 }