2973312_ac_187ms_196k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

struct point
{
	double x, y;
};

struct polygon
{
	char name;
	int v;
	point pt[21];
}p[27];

int n;

double max(double a,double b)
{
	return a > b ? a : b;
}

double min(double a,double b)
{
	return a < b ? a : b;
}

double multi(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool isIntersected(point s1,point e1,point s2,point e2)
{

    if(
		(max(s1.x, e1.x) >= min(s2.x, e2.x)) &&
		(max(s2.x, e2.x) >= min(s1.x, e1.x)) &&
		(max(s1.y, e1.y) >= min(s2.y, e2.y)) &&
		(max(s2.y, e2.y) >= min(s1.y, e1.y)) &&
		(multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) &&
		(multi(s1, e2, s2) * multi(e2, e1, s2) >= 0)
	 )
	 return true;
	 return false;
}

int check(polygon a,polygon b)
{
	int i, j;
	int na, nb;

	na = a.v;
	nb = b.v;
	for(i = 0; i < na; i++)
	{
		for(j = 0; j < nb; j++)
		{
			if(isIntersected(a.pt[i],a.pt[(i+1)%na],b.pt[j],b.pt[(j+1)%nb]))
				return 1;
		}
	}
	return 0;
}

bool cmp(polygon a,polygon b)
{
	return a.name < b.name;
}

int main()
{
	int i, j, num;
	char tmp[2];
	char style[10];
	int rel[27][27];
	point t;
	int cnt[27];

	while(scanf("%s",tmp)==1)
	{
		if(tmp[0]=='.')
			break;
		n = 0;
		while(tmp[0]!='-')
		{
			p[n].name = tmp[0];
			scanf("%s",style);
			getchar();
			if(strcmp(style,"line")==0)
				num = 2;
			else
				if(strcmp(style,"triangle")==0)
					num = 3;
				else
					if(strcmp(style,"square")==0)
						num = 4;
					else
						if(strcmp(style,"rectangle")==0)
							num = 4;
						else
						{
							scanf("%d",&num);
							getchar();
						}
			p[n].v = num;
			if((num!=4||strcmp(style,"polygon")==0)&&strcmp(style,"rectangle")!=0)
			{
				for(i = 0; i < num; i++)
				{
					scanf("(%lf,%lf)",&t.x,&t.y);
					getchar();
					p[n].pt[i] = t;
				}
			}
			else
			{
				if(style[0]=='s')
				{
					scanf("(%lf,%lf)",&t.x,&t.y);
					getchar();
					p[n].pt[0] = t;
					scanf("(%lf,%lf)",&t.x,&t.y);
					getchar();
					p[n].pt[2] = t;
					p[n].pt[1].x = (p[n].pt[0].x+p[n].pt[2].x+p[n].pt[2].y-p[n].pt[0].y)/2;
					p[n].pt[1].y = (p[n].pt[0].y+p[n].pt[2].y+p[n].pt[0].x-p[n].pt[2].x)/2;
					p[n].pt[3].x = (p[n].pt[0].x+p[n].pt[2].x+p[n].pt[0].y-p[n].pt[2].y)/2;
					p[n].pt[3].y = (p[n].pt[0].y+p[n].pt[2].y+p[n].pt[2].x-p[n].pt[0].x)/2;
				}
				else
				{
					for(i = 0; i < 3; i++)
					{
						scanf("(%lf,%lf)",&t.x,&t.y);
						getchar();
						p[n].pt[i] = t;
					}
					p[n].pt[3].y = p[n].pt[2].y+p[n].pt[0].y-p[n].pt[1].y;
					p[n].pt[3].x = p[n].pt[2].x+p[n].pt[0].x-p[n].pt[1].x;
				}
			}
			n++;
			scanf("%s",tmp);
		}
		sort(p,p+n,cmp);
		memset(rel,0,sizeof(rel));
		memset(cnt,0,sizeof(cnt));
		for(i = 0; i < n; i++)
		{
			for(j = i+1; j < n; j++)
			{
				rel[i][j] = rel[j][i] = check(p[i],p[j]);
				if(rel[i][j])
				{
					cnt[i]++;
					cnt[j]++;
				}
			}
		}
		for(i = 0; i < n; i++)
		{
			printf("%c ",p[i].name);
			if(cnt[i]==0)
			{
				puts("has no intersections");
				continue;
			}
			printf("intersects with ");
			if(cnt[i]==1)
			{
				for(j = 0; j < n; j++)
					if(rel[i][j])
					{
						printf("%c\n",p[j].name);
						break;
					}
				continue;
			}
			if(cnt[i]==2)
			{
				for(j = 0; j < n; j++)
					if(rel[i][j])
					{
						if(cnt[i]==2)
						{
							printf("%c",p[j].name);
							cnt[i]--;
						}
						else
						{
							printf(" and %c\n",p[j].name);
							break;
						}
					}
				continue;
			}
			for(j = 0; j < n; j++)
				if(rel[i][j])
				{
					if(cnt[i]>1)
					{
						printf("%c, ",p[j].name);
						cnt[i]--;
					}
					else
					{
						printf("and %c\n",p[j].name);
						break;
					}
				}
		}
		printf("\n");
	}
	return 0;
}