Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于AC了,注意图形只与另外两个相交是and前面没有逗号,附代码

Posted by dgzxzyf at 2022-08-12 16:11:14 on Problem 3449
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator