1 #include <iostream>  2 #include <stdio.h>  3 #include <string.h>  4 #include <algorithm>  5 #include <queue>  6 #include <map>  7 #include <vector>  8 #include <set>  9 #include <string> 10 #include <math.h> 11  12 using namespace std; 13 const double eps = 1e-8; 14 int sgn(double x) 15 { 16     if(fabs(x) < eps)return 0; 17     if(x < 0)return -1; 18     else return 1; 19 } 20 struct Point 21 { 22     double x,y; 23     Point(){} 24     Point(double _x,double _y) 25     { 26         x = _x;y = _y; 27     } 28     Point operator -(const Point &b)const 29     { 30         return Point(x - b.x,y - b.y); 31     } 32     //叉积 33     double operator ^(const Point &b)const 34     { 35         return x*b.y - y*b.x; 36     } 37     //点积 38     double operator *(const Point &b)const 39     { 40         return x*b.x + y*b.y; 41     } 42 }; 43 struct Line 44 { 45     Point s,e; 46     Line(){} 47     Line(Point _s,Point _e) 48     { 49         s = _s;e = _e; 50     } 51 }; 52 //*判断线段相交 53 bool inter(Line l1,Line l2) 54 { 55     return 56     max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) && 57     max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) && 58     max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) && 59     max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) && 60     sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0 && 61     sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= 0; 62 } 63  64 struct Node 65 { 66     char id; 67     int n;//点数 68     Point p[22]; 69 }node[30]; 70 bool cmp(Node a,Node b) 71 { 72     return a.id < b.id; 73 } 74 char str[30]; 75 bool check(Node a,Node b) 76 { 77     for(int i = 0;i < a.n;i++) 78         for(int j = 0;j < b.n;j++) 79            if(inter(Line(a.p[i],a.p[(i+1)%a.n]),Line(b.p[j],b.p[(j+1)%b.n]))) 80               return true; 81     return false; 82 } 83 bool ff[30]; 84 int main() 85 { 86     //freopen("in.txt","r",stdin); 87     //freopen("out.txt","w",stdout); 88     int n; 89     while(scanf("%s",str) == 1) 90     { 91         if(str[0] == ‘.‘)break; 92         node[0].id = str[0]; 93         scanf("%s",str); 94         if(strcmp(str,"square")==0) 95         { 96             node[0].n = 4; 97             scanf(" (%lf,%lf)",&node[0].p[0].x,&node[0].p[0].y); 98             //cout<<node[0].p[0].x<<" "<<node[0].p[0].y<<endl; 99             scanf(" (%lf,%lf)",&node[0].p[2].x,&node[0].p[2].y);100            // cout<<node[0].p[2].x<<" "<<node[0].p[2].y<<endl;101             node[0].p[1].x = ((node[0].p[0].x+node[0].p[2].x)+(node[0].p[2].y-node[0].p[0].y))/2;102             node[0].p[1].y = ((node[0].p[0].y+node[0].p[2].y)+(node[0].p[0].x-node[0].p[2].x))/2;103             node[0].p[3].x = ((node[0].p[0].x+node[0].p[2].x)-(node[0].p[2].y-node[0].p[0].y))/2;104             node[0].p[3].y = ((node[0].p[0].y+node[0].p[2].y)-(node[0].p[0].x-node[0].p[2].x))/2;105         }106         else if(strcmp(str,"line")==0)107         {108             node[0].n = 2;109             scanf(" (%lf,%lf)",&node[0].p[0].x,&node[0].p[0].y);110             scanf(" (%lf,%lf)",&node[0].p[1].x,&node[0].p[1].y);111         }112         else if(strcmp(str,"triangle")==0)113         {114             node[0].n = 3;115             scanf(" (%lf,%lf)",&node[0].p[0].x,&node[0].p[0].y);116             scanf(" (%lf,%lf)",&node[0].p[1].x,&node[0].p[1].y);117             scanf(" (%lf,%lf)",&node[0].p[2].x,&node[0].p[2].y);118         }119         else if(strcmp(str,"rectangle")==0)120         {121             node[0].n = 4;122             scanf(" (%lf,%lf)",&node[0].p[0].x,&node[0].p[0].y);123             scanf(" (%lf,%lf)",&node[0].p[1].x,&node[0].p[1].y);124             scanf(" (%lf,%lf)",&node[0].p[2].x,&node[0].p[2].y);125             node[0].p[3].x = node[0].p[2].x + (node[0].p[0].x - node[0].p[1].x);126             node[0].p[3].y = node[0].p[2].y + (node[0].p[0].y - node[0].p[1].y);127         }128         else if(strcmp(str,"polygon")==0)129         {130             scanf("%d",&node[0].n);131             for(int i = 0;i < node[0].n;i++)132             {133                 scanf(" (%lf,%lf)",&node[0].p[i].x,&node[0].p[i].y);134             }135         }136         n = 1;137         while(scanf("%s",str)==1)138         {139 140             //cout<<str<<endl;141             if(str[0] == ‘-‘)break;142             node[n].id = str[0];143             scanf("%s",str);144             if(strcmp(str,"square")==0)145             {146                 node[n].n = 4;147                 scanf(" (%lf,%lf)",&node[n].p[0].x,&node[n].p[0].y);148                 scanf(" (%lf,%lf)",&node[n].p[2].x,&node[n].p[2].y);149                 node[n].p[1].x = ((node[n].p[0].x+node[n].p[2].x)+(node[n].p[2].y-node[n].p[0].y))/2;150                 node[n].p[1].y = ((node[n].p[0].y+node[n].p[2].y)+(node[n].p[0].x-node[n].p[2].x))/2;151                 node[n].p[3].x = ((node[n].p[0].x+node[n].p[2].x)-(node[n].p[2].y-node[n].p[0].y))/2;152                 node[n].p[3].y = ((node[n].p[0].y+node[n].p[2].y)-(node[n].p[0].x-node[n].p[2].x))/2;153             }154             else if(strcmp(str,"line")==0)155             {156                 node[n].n = 2;157                 scanf(" (%lf,%lf)",&node[n].p[0].x,&node[n].p[0].y);158                 scanf(" (%lf,%lf)",&node[n].p[1].x,&node[n].p[1].y);159             }160             else if(strcmp(str,"triangle")==0)161             {162                 node[n].n = 3;163                 scanf(" (%lf,%lf)",&node[n].p[0].x,&node[n].p[0].y);164                 scanf(" (%lf,%lf)",&node[n].p[1].x,&node[n].p[1].y);165                 scanf(" (%lf,%lf)",&node[n].p[2].x,&node[n].p[2].y);166             }167             else if(strcmp(str,"rectangle")==0)168             {169                 node[n].n = 4;170                 scanf(" (%lf,%lf)",&node[n].p[0].x,&node[n].p[0].y);171                 scanf(" (%lf,%lf)",&node[n].p[1].x,&node[n].p[1].y);172                 scanf(" (%lf,%lf)",&node[n].p[2].x,&node[n].p[2].y);173                 node[n].p[3].x = node[n].p[2].x + (node[n].p[0].x - node[n].p[1].x);174                 node[n].p[3].y = node[n].p[2].y + (node[n].p[0].y - node[n].p[1].y);175             }176             else if(strcmp(str,"polygon")==0)177             {178                 scanf("%d",&node[n].n);179                 for(int i = 0;i < node[n].n;i++)180                 {181                     scanf(" (%lf,%lf)",&node[n].p[i].x,&node[n].p[i].y);182                 }183             }184             n++;185         }186         sort(node,node+n,cmp);187         for(int i = 0;i < n;i++)188         {189             printf("%c ",node[i].id);190             memset(ff,false,sizeof(ff));191             int cnt = 0;192             for(int j = 0;j < n;j++)193                 if(i != j)194                   if(check(node[i],node[j]))195                     {196                         cnt++;197                         ff[j] = true;198                     }199             if(cnt == 0)printf("has no intersections\n");200             else if(cnt == 1)201             {202                 printf("intersects with ");203                 for(int j = 0 ; j < n;j++)204                     if(ff[j])205                 {206                     printf("%c\n",node[j].id);207                     break;208                 }209             }210             else if(cnt == 2)211             {212                 printf("intersects with ");213                 for(int j = 0 ; j < n;j++)214                     if(ff[j])215                 {216                     if(cnt==2)printf("%c ",node[j].id);217                     if(cnt==1)printf("and %c\n",node[j].id);218                     cnt--;219                 }220             }221             else222             {223                 printf("intersects with ");224                 for(int j = 0 ; j < n;j++)225                     if(ff[j])226                 {227                     if(cnt > 1)printf("%c, ",node[j].id);228                     if(cnt==1)printf("and %c\n",node[j].id);229                     cnt--;230                 }231             }232         }233 234         printf("\n");235     }236 }