Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
终于AC了,注意图形只与另外两个相交是and前面没有逗号,附代码#include<iostream> #include<cstdio> #include<cmath> #include<map> #include<algorithm> using namespace std; const int N=30; struct node1 { double x,y; }l[N*20][2]; struct node2 { int size,id[N]; char s; }p[N]; char st,str[10],ans[N]; int cnt,tot; bool cmp(node2 a,node2 b) { return (int)a.s<(int)b.s; } bool judge(node1 a,node1 b,node1 c,node1 d) { if(min(a.x,b.x)>max(c.x,d.x)||min(c.x,d.x)>max(a.x,b.x)||min(a.y,b.y)>max(c.y,d.y)||min(c.y,d.y)>max(a.y,b.y)) return 0; else if(((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x))*((b.x-a.x)*(d.y-a.y)-(b.y-a.y)*(d.x-a.x))<=0&&((d.x-c.x)*(a.y-c.y)-(d.y-c.y)*(a.x-c.x))*((d.x-c.x)*(b.y-c.y)-(d.y-c.y)*(b.x-c.x))<=0) return 1; else return 0; } bool check(int x,int y) { for(int i=1;i<=p[x].size;i++) { for(int j=1;j<=p[y].size;j++) { if(judge(l[p[x].id[i]][0],l[p[x].id[i]][1],l[p[y].id[j]][0],l[p[y].id[j]][1])) return 1; } } return 0; } int main() { ios::sync_with_stdio(false); node1 a,b,c,d; while(cin>>st) { if(st=='.') break; cnt=tot=0; do { if(st=='-') break; p[++cnt].s=st; cin>>str; if(str[0]=='s') { cin>>st>>a.x>>st>>a.y>>st>>st>>b.x>>st>>b.y>>st; c.x=(a.x+b.x+a.y-b.y)/2,c.y=(a.y+b.y+b.x-a.x)/2; d.x=(a.x+b.x+b.y-a.y)/2,d.y=(a.y+b.y+a.x-b.x)/2; p[cnt].size=4; p[cnt].id[1]=++tot; l[tot][0]=a,l[tot][1]=c; p[cnt].id[2]=++tot; l[tot][0]=c,l[tot][1]=b; p[cnt].id[3]=++tot; l[tot][0]=b,l[tot][1]=d; p[cnt].id[4]=++tot; l[tot][0]=d,l[tot][1]=a; } else if(str[0]=='r') { cin>>st>>a.x>>st>>a.y>>st>>st>>b.x>>st>>b.y>>st>>st>>c.x>>st>>c.y>>st; d.x=a.x+c.x-b.x,d.y=a.y+c.y-b.y; p[cnt].size=4; p[cnt].id[1]=++tot; l[tot][0]=a,l[tot][1]=b; p[cnt].id[2]=++tot; l[tot][0]=b,l[tot][1]=c; p[cnt].id[3]=++tot; l[tot][0]=c,l[tot][1]=d; p[cnt].id[4]=++tot; l[tot][0]=d,l[tot][1]=a; } else if(str[0]=='l') { cin>>st>>a.x>>st>>a.y>>st>>st>>b.x>>st>>b.y>>st; p[cnt].size=1; p[cnt].id[1]=++tot; l[tot][0]=a,l[tot][1]=b; } else if(str[0]=='t') { cin>>st>>a.x>>st>>a.y>>st>>st>>b.x>>st>>b.y>>st>>st>>c.x>>st>>c.y>>st; p[cnt].size=3; p[cnt].id[1]=++tot; l[tot][0]=a,l[tot][1]=b; p[cnt].id[2]=++tot; l[tot][0]=b,l[tot][1]=c; p[cnt].id[3]=++tot; l[tot][0]=c,l[tot][1]=a; } else { cin>>p[cnt].size>>st>>a.x>>st>>a.y>>st; for(int i=1;i<p[cnt].size;i++) { cin>>st>>b.x>>st>>b.y>>st; p[cnt].id[i]=++tot; l[tot][0]=a,l[tot][1]=b; a.x=b.x,a.y=b.y; } p[cnt].id[p[cnt].size]=++tot; l[tot][0]=a,l[tot][1]=l[p[cnt].id[1]][0]; } }while(cin>>st); sort(p+1,p+1+cnt,cmp); for(int i=1;i<=cnt;i++) { int sum=0; for(int j=1;j<=cnt;j++) { if(i==j) continue; if(check(i,j)) ans[++sum]=p[j].s; } if(sum==0) printf("%c has no intersections\n",p[i].s); else if(sum==1) printf("%c intersects with %c\n",p[i].s,ans[1]); else if(sum==2) printf("%c intersects with %c and %c\n",p[i].s,ans[1],ans[2]); else { printf("%c intersects with ",p[i].s); for(int i=1;i<sum;i++) { printf("%c, ",ans[i]); } printf("and %c\n",ans[sum]); } } printf("\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator