3267176_wa.java

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

import java.util.*;

public class Main
{
    private Scanner in;
    final double eps = 1e-10;
    final double PAI = Math.PI;
    
    public static void main(String [] args)
    {
        new Main().run();
    }
    
    class Point
    {
        double x, y;
        public Point(double x,double y)
        {
            this.x = x;
            this.y = y;
        }
    }
    
    class Polygon
    {
        int num;
        Point p[];
        
        public Polygon()
        {
            num = in.nextInt();
            p = new Point [num+3];
            for(int i = 1; i <= num; i++)
            {
                p[i] = new Point(in.nextDouble(),in.nextDouble());
            }
            p[0] = new Point(p[num].x,p[num].y);
            p[num+1] = new Point(p[1].x,p[1].y);
            p[num+2] = new Point(p[2].x,p[2].y);
        }
    }
    
    public double dis(Point a,Point b)
    {
        return Math.hypot(a.x-b.x,a.y-b.y);
    }
    
    public void run()
    {
        Polygon p1, p2;
        int i, j;
        
        in = new Scanner (System.in);
        p1 = new Polygon();
        p2 = new Polygon();
        
        boolean 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 = Math.acos((ai*ai+bi*bi-di*di)/(2.0*ai*bi));
            alpha2 = Math.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(Math.abs(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 = Math.acos((aj*aj+bj*bj-dj*dj)/(2.0*aj*bj));
                beta2 = Math.acos((cj*cj+bj*bj-ej*ej)/(2.0*cj*bj));
                beta1 += alpha1;
                beta2 += alpha2;
                if(beta1 <= PAI + eps && beta2 <= PAI + eps)
                {
                    can = true;
                }
            }
        }
        System.out.println(can?"1":"0");
        in.close();
    }
}