1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 #include<map> 11 using namespace std; 12 #define N 600 13 #define LL long long 14 #define INF 0xfffffff 15 #define zero(x) (((x)>0?(x):-(x))<eps) 16 const double eps = 1e-8; 17 const double pi = acos(-1.0); 18 const double inf = ~0u>>2; 19 map<string,int>f; 20 vector<int>ed[30]; 21 int g; 22 struct point 23 { 24     double x,y; 25     point(double x=0,double y=0):x(x),y(y) {} 26 } p[600]; 27 typedef point pointt; 28 pointt operator -(point a,point b) 29 { 30     return pointt(a.x-b.x,a.y-b.y); 31 } 32 struct line 33 { 34     pointt u,v; 35     int flag; 36     char c; 37 } li[N]; 38 vector<line>dd[30]; 39 char s1[10],s2[15],s[30]; 40 int dcmp(double x) 41 { 42     if(fabs(x)<eps) return 0; 43     return x<0?-1:1; 44 } 45 point rotate(point a,double rad) 46 { 47     return point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad)); 48 } 49 double dot(point a,point b) 50 { 51     return a.x*b.x+a.y*b.y; 52 } 53 double dis(point a) 54 { 55     return sqrt(dot(a,a)); 56 } 57 double angle(point a,point b) 58 { 59     return acos(dot(a,b)/dis(a)/dis(b)); 60 } 61 double cross(point a,point b) 62 { 63     return a.x*b.y-a.y*b.x; 64 } 65  66 double xmult(point p1,point p2,point p0) 67 { 68     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 69 } 70 //判三点共线 71 int dots_inline(point p1,point p2,point p3) 72 { 73     return zero(xmult(p1,p2,p3)); 74 } 75  76 //判点是否在线段上,包括端点 77 int dot_online_in(point p,point l1,point l2) 78 { 79     return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps; 80 } 81  82 //判两点在线段同侧,点在线段上返回0 83  84 int same_side(point p1,point p2,point l1,point l2) 85 { 86     return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps; 87 } 88  89 //判两线段相交,包括端点和部分重合 90  91 int intersect_in(point u1,point u2,point v1,point v2) 92 { 93     if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2)) 94         return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2); 95     return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2); 96 } 97 void init(int kk,char c) 98 { 99     int i;100     int  k = c-‘A‘;101     if(kk==1)102     {103         for(i = 0; i <= 2 ; i+=2)104         {105             scanf(" (%lf,%lf)",&p[i].x,&p[i].y);106         }107         p[1].x=(p[0].x+p[2].x+p[2].y-p[0].y)/2;108         p[1].y=(p[0].y+p[2].y+p[0].x-p[2].x)/2;109         p[3].x=(p[0].x+p[2].x-p[2].y+p[0].y)/2;110         p[3].y=(p[0].y+p[2].y-p[0].x+p[2].x)/2;111         p[4] = p[0];112         for(i = 0; i < 4 ; i++)113         {114             li[++g].u = p[i];115             li[g].v = p[i+1];116             dd[k].push_back(li[g]);117         }118     }119     else if(kk==2)120     {121         for(i = 1; i <= 3 ; i++)122         {123             scanf(" (%lf,%lf)",&p[i].x,&p[i].y);124         }125         point pp = point((p[1].x+p[3].x),(p[1].y+p[3].y));126         p[4] = point(pp.x-p[2].x,pp.y-p[2].y);127         //printf("%.3f %.3f\n",p[4].x,p[4].y);128         p[5] = p[1];129         for(i = 1; i <= 4; i++)130         {131             li[++g].u = p[i];132             li[g].v = p[i+1];133             li[g].c = c;134             dd[k].push_back(li[g]);135         }136     }137     else if(kk==3)138     {139         for(i = 1; i <= 2; i++)140             scanf(" (%lf,%lf)",&p[i].x,&p[i].y);141         li[++g].u = p[1];142         li[g].v = p[2];143         li[g].c = c;144         dd[k].push_back(li[g]);145     }146     else if(kk==4)147     {148         for(i = 1; i <= 3 ; i++)149             scanf(" (%lf,%lf)",&p[i].x,&p[i].y);150         p[4] = p[1];151         for(i = 1; i <= 3 ; i++)152         {153             li[++g].u = p[i];154             li[g].v = p[i+1];155             li[g].c = c;156             dd[k].push_back(li[g]);157         }158     }159     else if(kk==5)160     {161         int n;162         scanf("%d",&n);163         for(i = 1; i <= n ; i++)164             scanf(" (%lf,%lf)",&p[i].x,&p[i].y);165         p[n+1] = p[1];166         for(i = 1; i <= n ; i++)167         {168             li[++g].u= p[i];169             li[g].v = p[i+1];170             li[g].c = c;171             dd[k].push_back(li[g]);172         }173     }174 }175 176 int main()177 {178     f["square"] = 1;179     f["rectangle"] = 2;180     f["line"] = 3;181     f["triangle"] = 4;182     f["polygon"] = 5;183     int i,j,k;184     while(scanf("%s",s1)!=EOF)185     {186         if(s1[0]==‘.‘) break;187         if(s1[0]==‘-‘) continue;188         for(i =0 ; i < 26 ; i++)189         {190             ed[i].clear();191             dd[i].clear();192         }193         g = 0;194         k=0;195         scanf("%s",s2);196         s[++k] = s1[0];197         init(f[s2],s1[0]);198         while(scanf("%s",s1)!=EOF)199         {200             if(s1[0]==‘-‘) break;201             //cout<<s1<<endl;202             scanf("%s",s2);203             s[++k] = s1[0];204             init(f[s2],s1[0]);205         }206         //cout<<g<<endl;207         sort(s+1,s+k+1);208         for(i = 1 ; i <= k; i++)209         {210             int u,v;211             u = s[i]-‘A‘;212             //cout<<u<<" "<<dd[u].size()<<endl;213             for(j = i+1; j <= k ; j++)214             {215                 v = s[j]-‘A‘;216                 int flag = 0;217                 for(int ii = 0 ; ii < dd[u].size() ; ii++)218                 {219                     for(int jj = 0 ; jj < dd[v].size() ; jj++)220                     {221                         if(intersect_in(dd[u][ii].u,dd[u][ii].v,dd[v][jj].u,dd[v][jj].v))222                         {223 224                             flag = 1;225                             break;226                         }227 //                    if(u==5&&v==22)228 //                        {229 //                            output(dd[u][ii].u);230 //                        output(dd[u][ii].v);231 //                        output(dd[v][jj].u);232 //                        output(dd[v][jj].v);233 //                        }234                     }235                     if(flag) break;236                 }237                 if(flag)238                 {239                     ed[u].push_back(v);240                     ed[v].push_back(u);241                 }242             }243         }244         for(i = 1 ; i <= k; i++)245         {246             int u = s[i]-‘A‘;247             if(ed[u].size()==0)248                 printf("%c has no intersections\n",s[i]);249             else250             {251 252                 sort(ed[u].begin(),ed[u].end());253                 if(ed[u].size()==1)254                     printf("%c intersects with %c\n",s[i],ed[u][0]+‘A‘);255                 else if(ed[u].size()==2)256                     printf("%c intersects with %c and %c\n",s[i],ed[u][0]+‘A‘,ed[u][1]+‘A‘);257                 else258                 {259                     printf("%c intersects with ",s[i]);260                     for(j = 0 ; j < ed[u].size()-1 ; j++)261                         printf("%c, ",ed[u][j]+‘A‘);262                     printf("and %c\n",ed[u][j]+‘A‘);263                 }264             }265         }266         puts("");267     }268     return 0;269 }