package geometry;

public class LineGeometry {
    static final double EPS = 1e-10;

    public static int sign(double a) {
        return a < -EPS ? -1 : a > EPS ? 1 : 0;
    }

    public static class Point implements Comparable<Point> {
        public double x, y;

        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public Point minus(Point b) {
            return new Point(x - b.x, y - b.y);
        }

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

        public double dot(Point b) {
            return x * b.x + y * b.y;
        }

        public Point rotateCCW(double angle) {
            return new Point(x * Math.cos(angle) - y * Math.sin(angle), x * Math.sin(angle) + y * Math.cos(angle));
        }

        @Override
        public int compareTo(Point o) {
            // return Double.compare(Math.atan2(y, x), Math.atan2(o.y, o.x));
            return Double.compare(x, o.x) != 0 ? Double.compare(x, o.x) : Double.compare(y, o.y);
        }
    }

    public static class Line {
        public double a, b, c;

        public Line(double a, double b, double c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        public Line(Point p1, Point p2) {
            a = +(p1.y - p2.y);
            b = -(p1.x - p2.x);
            c = p1.x * p2.y - p2.x * p1.y;
        }

        public Point intersect(Line line) {
            double d = a * line.b - line.a * b;
            if (sign(d) == 0) {
                return null;
            }
            double x = -(c * line.b - line.c * b) / d;
            double y = -(a * line.c - line.a * c) / d;
            return new Point(x, y);
        }
    }

    // Returns -1 for clockwise, 0 for straight line, 1 for counterclockwise order
    public static int orientation(Point a, Point b, Point c) {
        Point AB = b.minus(a);
        Point AC = c.minus(a);
        return sign(AB.cross(AC));
    }

    public static boolean cw(Point a, Point b, Point c) {
        return orientation(a, b, c) < 0;
    }

    public static boolean ccw(Point a, Point b, Point c) {
        return orientation(a, b, c) > 0;
    }

    public static boolean isCrossIntersect(Point a, Point b, Point c, Point d) {
        return orientation(a, b, c) * orientation(a, b, d) < 0 && orientation(c, d, a) * orientation(c, d, b) < 0;
    }

    public static boolean isCrossOrTouchIntersect(Point a, Point b, Point c, Point d) {
        if (Math.max(a.x, b.x) < Math.min(c.x, d.x) - EPS || Math.max(c.x, d.x) < Math.min(a.x, b.x) - EPS
            || Math.max(a.y, b.y) < Math.min(c.y, d.y) - EPS || Math.max(c.y, d.y) < Math.min(a.y, b.y) - EPS) {
            return false;
        }
        return orientation(a, b, c) * orientation(a, b, d) <= 0 && orientation(c, d, a) * orientation(c, d, b) <= 0;
    }

    public static double pointToLineDistance(Point p, Line line) {
        return Math.abs(line.a * p.x + line.b * p.y + line.c) / fastHypot(line.a, line.b);
    }

    public static double fastHypot(double x, double y) {
        return Math.sqrt(x * x + y * y);
    }

    public static double angleBetween(Point a, Point b) {
        return Math.atan2(a.cross(b), a.dot(b));
    }

    public static double angle(Line line) {
        return Math.atan2(-line.a, line.b);
    }

    // Usage example
    public static void main(String[] args) {}
}