import java.awt.geom.*;


/**
 * Created with IntelliJ IDEA.
 * User: Pavel Kunyavskiy
 * Date: 18/10/13
 * Time: 20:50
 */
public class SharedGeom {

    static class Line {
        long a, b, c;
        Line (int x1, int y1, int x2, int y2){
            a = y2 - y1;
            b = x1 - x2;
            c = -a*x1 - b*y1;
        }
        int side(int x, int y){
            long res = a*x + b*y + c;
            if (res > 0)
                return 1;
            if (res == 0)
                return 0;
            return -1;
        }
    }

    static boolean between(int l, int r, int x){
        if (l > r) {
            int t = l;
            l = r;
            r = t;
        }
        return l <= x && x <= r;
    }

    static boolean pointOnSegment(int x1, int y1,int x2,int y2,int x3,int y3){
        Line l = new Line(x1,y1, x2, y2);
        return l.side(x3, y3) == 0 && between(x1, x2, x3) && between(y1, y2, y3);
    }


    static boolean oldCheckSegmentIntersection(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
        return new Line2D.Double(x1, y1, x2, y2).intersectsLine(x3,y3,x4, y4);
    }

    static boolean newCheckSegmentIntersection(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
        Line l1 = new Line(x1, y1, x2, y2);
        Line l2 = new Line(x3, y3, x4, y4);

        if (pointOnSegment(x1, y1, x2, y2, x3, y3)) return true;
        if (pointOnSegment(x1, y1, x2, y2, x4, y4)) return true;
        if (pointOnSegment(x3, y3, x4, y4, x1, y1)) return true;
        if (pointOnSegment(x3, y3, x4, y4, x2, y2)) return true;


        if (l1.side(x3, y3) * l1.side(x4, y4) >= 0)
            return false;

        if (l2.side(x1, y1) * l2.side(x2, y2) >= 0)
            return false;

        return true;
    }

    static boolean checkSegmentIntersection(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
        boolean res1 = newCheckSegmentIntersection(x1, y1, x2, y2, x3, y3, x4, y4);
        boolean res2 = oldCheckSegmentIntersection(x1, y1, x2, y2, x3, y3, x4, y4);
        if (res1 != res2){
            //System.err.println("Fail");
            throw new AssertionError("res1 == res2");
        }
        //System.err.println("OK");
        return res1;
    }

    static boolean checkInside(int[] x, int[] y, int x0, int y0){
        int n = x.length;
        for (int i = 0; i < n; i++)
            if (pointOnSegment(x[i], y[i], x[(i+1) %n], y[(i+1)%n], x0, y0))
                return true;
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (checkSegmentIntersection(x[i], y[i], x[(i+1) %n], y[(i+1)%n], x0, y0, (int)1e7, y0+1))
                cnt++;
        return cnt % 2 == 1;
    }

    /*static Point2D getPolygonCenter(int[] x, int[] y){
        throw new RuntimeException("getPolygonCenter shouldn't be used now.");
        long sumx, sumy;
        sumx = sumy = 0;
        int n = x.length;
        long s = 0;
        for (int i = 0; i < n; i++){
            long ds = x[(i+1)%n] * (long)y[i] - y[(i+1)%n] * (long)x[i];
            sumx += (x[i] + x[(i+1)%n]) * ds;
            sumy += (y[i] + y[(i+1)%n]) * ds;
            s += ds;
        }
        return new Point2D.Double(sumx/(double)(3*s), sumy/(double)(3*s));
    }*/

    /*static Path2D getPolygon(int[] x, int[] y){
        Point2D center;
        center = getPolygonCenter(x, y);
        Path2D polygon = new Path2D.Double();
        polygon.moveTo(x[0],y[0]);
        for (int i = 1; i < x.length; i++)
            polygon.lineTo(x[i], y[i]);
        polygon.lineTo(x[0],y[0]);

        double theta = -Math.PI/2 - Math.atan2(center.getY() - y[0], center.getX() - x[0]);
        polygon.transform(AffineTransform.getRotateInstance(theta, x[0], y[0]));

        return polygon;
    }*/

   /* public static Point2D getRotatedPolygonCenter(int[] x, int[] y) {
        throw new RuntimeException("getRotatedPolygonCenter shouldn't be used now.");

        Point2D center;
        center = getPolygonCenter(x, y);
        double theta = -Math.PI/2 - Math.atan2(center.getY() - y[0], center.getX() - x[0]);
        return AffineTransform.getRotateInstance(theta, x[0], y[0]).transform(center,null);
    }*/
}
