题目链接：https://vjudge.net/problem/POJ-3449
题意：给出若干几何体，判断每个几何体与其它几何体的相交情况，并依次输出。
思路：
首先要知道的是根据正方形对角线的两个点怎么求其它两个点，比如已知(x0,y0),(x2,y2)，那么：
x1+x3=x0+x2,
x1-x3=y2-y0,
y1+y3=y0+y2,
y1-y3=x0-x2
之后就暴力枚举了，枚举所有几何体的所有边，用线段相交判断几何体相交。这题的输入输出很恶心。
AC代码：
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std; const double eps=1e-;
int sgn(double x){
if(abs(x)<eps) return ;
else if(x<) return -;
else return ;
} struct Point{
double x,y;
Point(){}
Point(double xx,double yy){
x=xx,y=yy;
}
Point operator + (const Point& b)const{
return Point(x+b.x,y+b.y);
}
Point operator - (const Point& b)const{
return Point(x-b.x,y-b.y);
}
double operator ^ (const Point& b)const{
return x*b.y-y*b.x;
}
}; struct Line{
Point s,e;
Line(){}
Line(Point ss,Point ee){
s=ss,e=ee;
}
}; bool inter(Line l1,Line l2){
return
max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&&
max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&&
max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&&
max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&&
sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=&&
sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e))<=;
} struct node{
char id;
int num;
Point pt[];
}sp[]; bool cmp(node a,node b){
return a.id<b.id;
} bool check(node a,node b){
for(int i=;i<a.num;++i)
for(int j=;j<b.num;++j)
if(inter(Line(a.pt[i],a.pt[(i+)%a.num]),Line(b.pt[j],b.pt[(j+)%b.num])))
return true;
return false;
} vector<char> vc;
int n;
char str[]; int main(){
while(scanf("%s",str),str[]!='.'){
sp[].id=str[];
scanf("%s",str);
if(strcmp(str,"square")==){
sp[].num=;
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
sp[].pt[].x=(sp[].pt[].x+sp[].pt[].x+(sp[].pt[].y-sp[].pt[].y))/;
sp[].pt[].x=(sp[].pt[].x+sp[].pt[].x-(sp[].pt[].y-sp[].pt[].y))/;
sp[].pt[].y=(sp[].pt[].y+sp[].pt[].y+(sp[].pt[].x-sp[].pt[].x))/;
sp[].pt[].y=(sp[].pt[].y+sp[].pt[].y-(sp[].pt[].x-sp[].pt[].x))/;
}
else if(strcmp(str,"rectangle")==){
sp[].num=;
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
sp[].pt[].x=sp[].pt[].x+(sp[].pt[].x-sp[].pt[].x);
sp[].pt[].y=sp[].pt[].y+(sp[].pt[].y-sp[].pt[].y);
}
else if(strcmp(str,"line")==){
sp[].num=;
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
}
else if(strcmp(str,"triangle")==){
sp[].num=;
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
scanf(" (%lf,%lf)",&sp[].pt[].x,&sp[].pt[].y);
}
else{
scanf("%d",&sp[].num);
for(int i=;i<sp[].num;++i)
scanf(" (%lf,%lf)",&sp[].pt[i].x,&sp[].pt[i].y);
}
n=;
while(scanf("%s",str),str[]!='-'){
sp[n].id=str[];
scanf("%s",str);
if(strcmp(str,"square")==){
sp[n].num=;
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
sp[n].pt[].x=(sp[n].pt[].x+sp[n].pt[].x+(sp[n].pt[].y-sp[n].pt[].y))/;
sp[n].pt[].x=(sp[n].pt[].x+sp[n].pt[].x-(sp[n].pt[].y-sp[n].pt[].y))/;
sp[n].pt[].y=(sp[n].pt[].y+sp[n].pt[].y+(sp[n].pt[].x-sp[n].pt[].x))/;
sp[n].pt[].y=(sp[n].pt[].y+sp[n].pt[].y-(sp[n].pt[].x-sp[n].pt[].x))/;
}
else if(strcmp(str,"rectangle")==){
sp[n].num=;
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
sp[n].pt[].x=sp[n].pt[].x+(sp[n].pt[].x-sp[n].pt[].x);
sp[n].pt[].y=sp[n].pt[].y+(sp[n].pt[].y-sp[n].pt[].y);
}
else if(strcmp(str,"line")==){
sp[n].num=;
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
}
else if(strcmp(str,"triangle")==){
sp[n].num=;
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
scanf(" (%lf,%lf)",&sp[n].pt[].x,&sp[n].pt[].y);
}
else{
scanf("%d",&sp[n].num);
for(int i=;i<sp[n].num;++i)
scanf(" (%lf,%lf)",&sp[n].pt[i].x,&sp[n].pt[i].y);
}
++n;
}
sort(sp,sp+n,cmp);
for(int i=;i<n;++i){
printf("%c ",sp[i].id);
vc.clear();
for(int j=;j<n;++j)
if(j!=i)
if(check(sp[i],sp[j]))
vc.push_back(sp[j].id);
if(vc.size()==){
printf("has no intersections\n");
}
else if(vc.size()==){
printf("intersects with %c\n",vc[]);
}
else if(vc.size()==){
printf("intersects with %c and %c\n",vc[],vc[]);
}
else{
printf("intersects with ");
for(int j=;j<vc.size()-;++j)
printf("%c, ",vc[j]);
printf("and %c\n",vc[vc.size()-]);
}
}
printf("\n");
}
return ;
}