3255923_ac_235ms_200k.cpp

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

#include <stdio.h>

struct point
{
	double x, y;
}ants[100], apple[100];

int link[100];

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);
}

int 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 1;
	 return 0;
}

int main()
{
	int i, j, n, f, ti, tj;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%lf%lf",&ants[i].x,&ants[i].y);
	}
	for(i = 0; i < n; i++)
	{
		scanf("%lf%lf",&apple[i].x,&apple[i].y);
	}
	for(i = 0; i < n; i++)
	{
		link[i] = i;
	}
	while(1)
	{
		f = 0;
		for(i = 0; i < n; i++)
		{
			for(j = i+1; j < n; j++)
			{
				ti = link[i];
				tj = link[j];
				if(isIntersected(ants[i],apple[ti],ants[j],apple[tj]))
				{
					f = 1;
					link[i] = tj;
					link[j] = ti;
				}
			}
			if(f==1)
			{
				break;
			}
		}
		if(f==0)
		{
			break;
		}
	}
	for(i = 0; i < n; i++)
	{
		printf("%d\n",link[i]+1);
	}
	return 0;
}