3268351_ac_0ms_212k.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;
}

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

double cross(Point a1, Point a2, Point b1, Point b2)
{
    Point a, b;
    a.x = a2.x - a1.x;
    a.y = a2.y - a1.y;
    b.x = b2.x - b1.x;
    b.y = b2.y - b1.y;
    return cross(a, b);
}

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+1)%p1.num],p1.p[i%p1.num],p1.p[(i-1+p1.num)%p1.num])+angle(p2.p[(j-1+p2.num)%p2.num],p2.p[j],p2.p[(j+1)%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;
			
			int now1 = (i + k) % p1.num, now2 = (now1 + 1) % p1.num, now3 = (now2 + 1) % p1.num;
            int flag = 1;
            while (now2 != i)
            {
                if (cross(p1.p[now1], p1.p[now2], p1.p[now2], p1.p[now3]) < 0)
                {
                    flag = 0;
                    break;
                }
                now1 = now2;
                now2 = now3;
                now3 = (now3 + 1) % p1.num;
            }
            if (flag == 0)
                continue;
 
            now1 = (j + k) % p2.num, now2 = (now1 + 1) % p2.num, now3 = (now2 + 1) % p2.num;
            flag = 1;
            while (now2 != j)
            {
                if (cross(p2.p[now1], p2.p[now2], p2.p[now2], p2.p[now3]) > 0)
                {
                    flag = 0;
                    break;
                }
                now1 = now2;
                now2 = now3;
                now3 = (now3 + 1) % p2.num;
            }
            if (flag == 0)
                continue;

			can = true;
		}
	}
	puts(can?"1":"0");
	return 0;
}