3268156_wa.cpp

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

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

using namespace std;

double PAI = acos(-1.0);
double eps = 1e-3;

class Point
{
public:
	double x, y;
   
	Point(double xx,double yy)
	{
		x = xx;
		y = yy;
	}

	Point()
	{
	}
};

double cross(Point a,Point b,Point c)
{
	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

class Polygon
{
public:
	int num;
	Point p[100];
    
	Polygon(int b)
	{
		scanf("%d",&num);
		int st, ed, inc;

		if(b==0)
		{
			st = 0;
			ed = num;
			inc = 1;
		}
		else
		{
			st = num-1;
			ed = -1;
			inc = -1;
		}
		for(int i = st; i != ed; i += inc)
		{
			double x, y;
			scanf("%lf%lf",&x,&y);
			p[i] = Point(x,y);
		}
	}
};

double dis(Point a,Point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double angle(Point a,Point b,Point c)
{
	int flag = 1;

	if(cross(c,a,b) < 0)
		flag = 0;
	double A = dis(a,b);
	double B = dis(b,c);
	double C = dis(a,c);
	double alpha = acos((A*A+B*B-C*C)/(2.0*A*B));
	if(flag)
	{
		alpha = 2.0 * PAI - alpha;
	}
	return alpha;
}

int main()
{
	Polygon p1 = Polygon(0);
	Polygon p2 = Polygon(1);
	int i, j, k;

	bool can = false;
	
	for(i = 0; !can && i < p1.num; i++)
	{
		for(j = 0; !can && j < p2.num; j++)
		{
			if(fabs(dis(p1.p[i],p1.p[(i+1)%p1.num])-dis(p2.p[j],p2.p[(j+1)%p2.num])) > eps)
			{
				continue;
			}
			if(angle(p1.p[(i+2)%p1.num],p1.p[(i+1)%p1.num],p1.p[i])+angle(p2.p[j],p2.p[(j+1)%p2.num],p2.p[(j+2)%p2.num]) > PAI + eps)
			{
				continue;
			}
			k = 1;
			while(1)
			{
				if(fabs(dis(p1.p[(i+k)%p1.num],p1.p[(i+k+1)%p1.num])-dis(p2.p[(j+k)%p2.num],p2.p[(j+k+1)%p2.num])) > eps)
					break;
				if(fabs(angle(p1.p[(i+k-1)%p1.num],p1.p[(i+k)%p1.num],p1.p[(i+k+1)%p1.num])-angle(p2.p[(j+k-1)%p2.num],p2.p[(j+k)%p2.num],p2.p[(j+k+1)%p2.num])) > eps)
					break;
				k++;
			}
			if(angle(p1.p[(i+k+1)%p1.num],p1.p[(i+k)%p1.num],p1.p[(i+k-1)%p1.num])+angle(p2.p[(j+k-1)%p2.num],p2.p[(j+k)%p2.num],p2.p[(j+k+1)%p2.num]) > PAI + eps)
				continue;
			can = true;
		}
	}
	puts(can?"1":"0");
	return 0;
}