3267288_ce.cpp

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

#include <stdio.h>
#include <math.h>

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()
	{
	}

};

class Polygon
{
public:
    int num;
    Point p[110];
    
    Polygon()
    {
        scanf("%d",&num);
        for(int i = 1; i <= num; i++)
        {
			double x, y;
			scanf("%lf%lf",&x,&y);
            p[i] = Point(x,y);
        }
        p[0] = Point(p[num].x,p[num].y);
        p[num+1] = Point(p[1].x,p[1].y);
        p[num+2] = Point(p[2].x,p[2].y);
    }
};

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

int main()
{
	Polygon p1 = Polygon();
	Polygon p2 = Polygon();
    int i, j;
    
    bool can = false;
    double ai, bi, ci, di, ei;
    double aj, bj, cj, dj, ej;
    double alpha1, alpha2, beta1, beta2;
    
    for(i = 1; !can && i <= p1.num; i++)
    {
        ai = dis(p1.p[i],p1.p[i-1]);
        bi = dis(p1.p[i],p1.p[i+1]);
        ci = dis(p1.p[i+1],p1.p[i+2]);
        di = dis(p1.p[i-1],p1.p[i+1]);
        ei = dis(p1.p[i],p1.p[i+2]);
        alpha1 = acos((ai*ai+bi*bi-di*di)/(2.0*ai*bi));
        alpha2 = acos((ci*ci+bi*bi-ei*ei)/(2.0*ci*bi));
        for(j = 2; !can && j <= p2.num+1; j++)
        {
            bj = dis(p2.p[j],p2.p[j-1]);
            if(fabs(bi-bj) > eps)
            {
                continue;
            }
            aj = dis(p2.p[j-1],p2.p[j-2]);
            cj = dis(p2.p[j],p2.p[j+1]);
            dj = dis(p2.p[j],p2.p[j-2]);
            ej = dis(p2.p[j-1],p2.p[j+1]);
            beta1 = acos((aj*aj+bj*bj-dj*dj)/(2.0*aj*bj));
            beta2 = acos((cj*cj+bj*bj-ej*ej)/(2.0*cj*bj));
            beta1 += alpha1;
            beta2 += alpha2;
            if(beta1 <= PAI + eps && beta2 <= PAI + eps)
            {
                can = true;
            }
        }
    }
    puts(can?"1":"0");
	return 0;
}