| ||||||||||
| 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