using System;
using System.Drawing;

namespace Contours {
    public static class Geometry {
        public enum IntersectionType {
            None,
            Cross,
            Identical,
            Inverted,
            Touch_a0,
            Touch_a1,
            Touch_b0,
            Touch_b1,
            Touch_a0_b0,
            Touch_a0_b1,
            Touch_a1_b0,
            Touch_a1_b1,
            Along_a0_b0_a1_b1,
            Along_a0_b0_b1_a1,
            Along_a0_b1_a1_b0,
            Along_a0_b1_b0_a1,
            Along_b0_a0_a1_b1,
            Along_b0_a0_b1_a1,
            Along_b1_a0_a1_b0,
            Along_b1_a0_b0_a1
        }

        // Compare to points place at line base0-base1
        public static int comparePointsAtLine(Point a0, Point a1, Point base0, Point base1) {
            if (base0.X < base1.X && a0.X < a1.X) return -1;
            if (base0.X < base1.X && a1.X < a0.X) return  1;
            if (base1.X < base0.X && a0.X < a1.X) return  1;
            if (base1.X < base0.X && a1.X < a0.X) return -1;
            if (base0.Y < base1.Y && a0.Y < a1.Y) return -1;
            if (base0.Y < base1.Y && a1.Y < a0.Y) return  1;
            if (base1.Y < base0.Y && a0.Y < a1.Y) return  1;
            if (base1.Y < base0.Y && a1.Y < a0.Y) return -1;
            return 0;
        }

        public static IntersectionType findIntersection(Point a0, Point a1, Point b0, Point b1, out Point c) {
            c = new Point(0, 0);
            Point da = new Point(a1.X - a0.X, a1.Y - a0.Y);
            Point db = new Point(b1.X - b0.X, b1.Y - b0.Y);

            if (a0.X == b0.X && a0.Y == b0.Y && a1.X == b1.X && a1.Y == b1.Y)
                return IntersectionType.Identical;

            if (a0.X == b1.X && a0.Y == b1.Y && a1.X == b0.X && a1.Y == b0.Y)
                return IntersectionType.Inverted;

            long divider = (long)da.X*(long)db.Y - (long)db.X*(long)da.Y;
            if (divider == 0) {
                if ((long)da.X*(long)(b0.Y - a0.Y) != (long)da.Y*(long)(b0.X - a0.X))
                    return IntersectionType.None;

                int a0b0 = comparePointsAtLine(a0, b0, a0, a1);
                int a0b1 = comparePointsAtLine(a0, b1, a0, a1);
                int a1b0 = comparePointsAtLine(a1, b0, a0, a1);
                int a1b1 = comparePointsAtLine(a1, b1, a0, a1);
                int b0b1 = comparePointsAtLine(b0, b1, a0, a1);
                int b0a0 = -a0b0;
                int b0a1 = -a1b0;
                int b1a0 = -a0b1;
                int b1a1 = -a1b1;
                int b1b0 = -b0b1;

                // a0a1b0b1
                if (a1b0 == 0 && b0b1 <= 0)
                    return IntersectionType.Touch_a1_b0;
                // a0a1b1b0
                if (a1b1 == 0 && b1b0 <= 0)
                    return IntersectionType.Touch_a1_b1;
                // b0b1a0a1
                if (b0b1 <= 0 && b1a0 == 0)
                    return IntersectionType.Touch_a0_b1;
                // b1b0a0a1
                if (b1b0 <= 0 && b0a0 == 0)
                    return IntersectionType.Touch_a0_b0;

                if (a0b0 <= 0 && b0a1 <= 0 && a1b1 <= 0)
                    return IntersectionType.Along_a0_b0_a1_b1;
                if (a0b0 <= 0 && b0b1 <= 0 && b1a1 <= 0)
                    return IntersectionType.Along_a0_b0_b1_a1;
                if (a0b1 <= 0 && b1a1 <= 0 && a1b0 <= 0)
                    return IntersectionType.Along_a0_b1_a1_b0;
                if (a0b1 <= 0 && b1b0 <= 0 && b0a1 <= 0)
                    return IntersectionType.Along_a0_b1_b0_a1;
                if (b0a0 <= 0 && /*  a0a1  */ a1b1 <= 0)
                    return IntersectionType.Along_b0_a0_a1_b1;
                if (b0a0 <= 0 && a0b1 <= 0 && b1a1 <= 0)
                    return IntersectionType.Along_b0_a0_b1_a1;
                if (b1a0 <= 0 && /*  a0a1  */ a1b0 <= 0)
                    return IntersectionType.Along_b1_a0_a1_b0;
                if (b1a0 <= 0 && a0b0 <= 0 && b0a1 <= 0)
                    return IntersectionType.Along_b1_a0_b0_a1;

                return IntersectionType.None;
            }

            if (a0.X == b0.X && a0.Y == b0.Y)
                return IntersectionType.Touch_a0_b0;
            if (a0.X == b1.X && a0.Y == b1.Y)
                return IntersectionType.Touch_a0_b1;
            if (a1.X == b0.X && a1.Y == b0.Y)
                return IntersectionType.Touch_a1_b0;
            if (a1.X == b1.X && a1.Y == b1.Y)
                return IntersectionType.Touch_a1_b1;

            long numeratorX = (long)da.X*((long)b1.Y*(long)b0.X - (long)b0.Y*(long)b1.X)
                            - (long)db.X*((long)a1.Y*(long)a0.X - (long)a0.Y*(long)a1.X);
            long numeratorY = (long)db.Y*((long)a1.X*(long)a0.Y - (long)a0.X*(long)a1.Y)
                            - (long)da.Y*((long)b1.X*(long)b0.Y - (long)b0.X*(long)b1.Y);
            Point p = new Point((int)(numeratorX/divider), (int)(numeratorY/divider));
            if ( comparePointsAtLine(p, a0, a0, a1) < 0
              || comparePointsAtLine(p, a1, a0, a1) > 0
              || comparePointsAtLine(p, b0, b0, b1) < 0
              || comparePointsAtLine(p, b1, b0, b1) > 0 )
                return IntersectionType.None;

            if (p.X == a0.X && p.Y == a0.Y)
                return IntersectionType.Touch_a0;
            if (p.X == a1.X && p.Y == a1.Y)
                return IntersectionType.Touch_a1;
            if (p.X == b0.X && p.Y == b0.Y)
                return IntersectionType.Touch_b0;
            if (p.X == b1.X && p.Y == b1.Y)
                return IntersectionType.Touch_b1;

            c = p;
            return IntersectionType.Cross;
        }
        
        public static bool isCCW(Point a, Point b, Point c) {
            long d = (long)a.X*(long)c.Y - (long)a.Y*(long)c.X;
            // angle AC < 180 deg
            if (d > 0)
                return (long)a.X*(long)b.Y >= (long)a.Y*(long)b.X
                    && (long)c.X*(long)b.Y <= (long)c.Y*(long)b.X;
            // angle AC > 180 deg
            if (d < 0)
                return (long)a.X*(long)b.Y >= (long)a.Y*(long)b.X
                    || (long)c.X*(long)b.Y <= (long)c.Y*(long)b.X;
            // angle AC == 180 deg
            if ((a.X >= 0) != (c.X >= 0) || (a.Y >= 0) != (c.Y >= 0))
                return (long)a.X*(long)b.Y >= (long)a.Y*(long)b.X;
            // angle AC == 0 deg
            return true;
        }

        public static bool isCCW(Point center, Point a, Point b, Point c) {
            return isCCW(
                new Point(a.X - center.X, a.Y - center.Y),
                new Point(b.X - center.X, b.Y - center.Y),
                new Point(c.X - center.X, c.Y - center.Y) );
        }
        
        public static void makeLongestLine(Point p0, ref Point p1) {
            int MaxValue = int.MaxValue << 1;
            Point direction = new Point(p1.X - p0.X, p1.Y - p0.Y);
            int amplifierX =
                direction.X > 0 ? (MaxValue - p0.X)/direction.X + 1
              : direction.X < 0 ? (MaxValue + p0.X)/(-direction.X) + 1
              : int.MaxValue;
            int amplifierY =
                direction.Y > 0 ? (MaxValue - p0.Y)/direction.Y + 1
              : direction.Y < 0 ? (MaxValue + p0.Y)/(-direction.Y) + 1
              : int.MaxValue;
            int amplifier = Math.Min(amplifierX, amplifierY);
            p1 = new Point(
                    p0.X + direction.X*amplifier,
                    p0.Y + direction.Y*amplifier );
        }
                
    }
}