繁琐。
处理出来所有的线段，再判断相交。
对于正方形的已知对角顶点求剩余两顶点 （列出4个方程求解）
p[].x=(p[].x+p[].x+p[].y-p[].y)/;
p[].y=(p[].y+p[].y+p[].x-p[].x)/;
p[].x=(p[].x+p[].x-p[].y+p[].y)/;
p[].y=(p[].y+p[].y-p[].x+p[].x)/;
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define N 600
#define LL long long
#define INF 0xfffffff
#define zero(x) (((x)>0?(x):-(x))<eps)
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
map<string,int>f;
vector<int>ed[];
int g;
struct point
{
double x,y;
point(double x=,double y=):x(x),y(y) {}
} p[];
typedef point pointt;
pointt operator -(point a,point b)
{
return pointt(a.x-b.x,a.y-b.y);
}
struct line
{
pointt u,v;
int flag;
char c;
} li[N];
vector<line>dd[];
char s1[],s2[],s[];
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
point rotate(point a,double rad)
{
return point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
double dot(point a,point b)
{
return a.x*b.x+a.y*b.y;
}
double dis(point a)
{
return sqrt(dot(a,a));
}
double angle(point a,point b)
{
return acos(dot(a,b)/dis(a)/dis(b));
}
double cross(point a,point b)
{
return a.x*b.y-a.y*b.x;
} double xmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//判三点共线
int dots_inline(point p1,point p2,point p3)
{
return zero(xmult(p1,p2,p3));
} //判点是否在线段上,包括端点
int dot_online_in(point p,point l1,point l2)
{
return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
} //判两点在线段同侧,点在线段上返回0 int same_side(point p1,point p2,point l1,point l2)
{
return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
} //判两线段相交,包括端点和部分重合 int intersect_in(point u1,point u2,point v1,point v2)
{
if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
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);
}
void init(int kk,char c)
{
int i;
int k = c-'A';
if(kk==)
{
for(i = ; i <= ; i+=)
{
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
}
p[].x=(p[].x+p[].x+p[].y-p[].y)/;
p[].y=(p[].y+p[].y+p[].x-p[].x)/;
p[].x=(p[].x+p[].x-p[].y+p[].y)/;
p[].y=(p[].y+p[].y-p[].x+p[].x)/;
p[] = p[];
for(i = ; i < ; i++)
{
li[++g].u = p[i];
li[g].v = p[i+];
dd[k].push_back(li[g]);
}
}
else if(kk==)
{
for(i = ; i <= ; i++)
{
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
}
point pp = point((p[].x+p[].x),(p[].y+p[].y));
p[] = point(pp.x-p[].x,pp.y-p[].y);
//printf("%.3f %.3f\n",p[4].x,p[4].y);
p[] = p[];
for(i = ; i <= ; i++)
{
li[++g].u = p[i];
li[g].v = p[i+];
li[g].c = c;
dd[k].push_back(li[g]);
}
}
else if(kk==)
{
for(i = ; i <= ; i++)
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
li[++g].u = p[];
li[g].v = p[];
li[g].c = c;
dd[k].push_back(li[g]);
}
else if(kk==)
{
for(i = ; i <= ; i++)
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
p[] = p[];
for(i = ; i <= ; i++)
{
li[++g].u = p[i];
li[g].v = p[i+];
li[g].c = c;
dd[k].push_back(li[g]);
}
}
else if(kk==)
{
int n;
scanf("%d",&n);
for(i = ; i <= n ; i++)
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
p[n+] = p[];
for(i = ; i <= n ; i++)
{
li[++g].u= p[i];
li[g].v = p[i+];
li[g].c = c;
dd[k].push_back(li[g]);
}
}
} int main()
{
f["square"] = ;
f["rectangle"] = ;
f["line"] = ;
f["triangle"] = ;
f["polygon"] = ;
int i,j,k;
while(scanf("%s",s1)!=EOF)
{
if(s1[]=='.') break;
if(s1[]=='-') continue;
for(i = ; i < ; i++)
{
ed[i].clear();
dd[i].clear();
}
g = ;
k=;
scanf("%s",s2);
s[++k] = s1[];
init(f[s2],s1[]);
while(scanf("%s",s1)!=EOF)
{
if(s1[]=='-') break;
//cout<<s1<<endl;
scanf("%s",s2);
s[++k] = s1[];
init(f[s2],s1[]);
}
//cout<<g<<endl;
sort(s+,s+k+);
for(i = ; i <= k; i++)
{
int u,v;
u = s[i]-'A';
//cout<<u<<" "<<dd[u].size()<<endl;
for(j = i+; j <= k ; j++)
{
v = s[j]-'A';
int flag = ;
for(int ii = ; ii < dd[u].size() ; ii++)
{
for(int jj = ; jj < dd[v].size() ; jj++)
{
if(intersect_in(dd[u][ii].u,dd[u][ii].v,dd[v][jj].u,dd[v][jj].v))
{ flag = ;
break;
}
// if(u==5&&v==22)
// {
// output(dd[u][ii].u);
// output(dd[u][ii].v);
// output(dd[v][jj].u);
// output(dd[v][jj].v);
// }
}
if(flag) break;
}
if(flag)
{
ed[u].push_back(v);
ed[v].push_back(u);
}
}
}
for(i = ; i <= k; i++)
{
int u = s[i]-'A';
if(ed[u].size()==)
printf("%c has no intersections\n",s[i]);
else
{ sort(ed[u].begin(),ed[u].end());
if(ed[u].size()==)
printf("%c intersects with %c\n",s[i],ed[u][]+'A');
else if(ed[u].size()==)
printf("%c intersects with %c and %c\n",s[i],ed[u][]+'A',ed[u][]+'A');
else
{
printf("%c intersects with ",s[i]);
for(j = ; j < ed[u].size()- ; j++)
printf("%c, ",ed[u][j]+'A');
printf("and %c\n",ed[u][j]+'A');
}
}
}
puts("");
}
return ;
}