1 files changed, 141 insertions, 0 deletions
diff --git a/Algorithms/Part-I/3-Collinear/Fast.java b/Algorithms/Part-I/3-Collinear/Fast.java
new file mode 100644
index 0000000..2640d65
--- /dev/null
+++ b/Algorithms/Part-I/3-Collinear/Fast.java
@@ -0,0 +1,141 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Arrays;
+
+public class Fast
+{
+
+    public static void main(String[] args)
+    {
+        class Solution implements Comparable<Solution>
+        {
+            private Point[] pts;
+            private int n = 0;
+
+            public Solution(int n)
+            {
+                pts = new Point[n];
+            }
+
+            public void add(Point p)
+            {
+                pts[n++] = p;
+            }
+
+            public void sort()
+            {
+                Insertion.sort(pts);
+            }
+
+            public void draw()
+            {
+                pts[0].drawTo(pts[n - 1]);
+            }
+
+            public void print()
+            {
+                String out = "";
+                for (int i = 0; i < n; i++)
+                    out += pts[i]+" -> ";
+                System.out.println(out.substring(0, (out.length() - 4)));
+            }
+
+            public boolean equals(Object o)
+            {
+                if (o == this) return true;
+                if (o == null) return false;
+                if (o.getClass() != this.getClass()) return false;
+
+                Solution other = (Solution) o;
+                if (n != other.n) return false;
+
+                for (int i = 0; i < n; i++)
+                    if (pts[i] != other.pts[i])
+                        return false;
+                return true;
+
+            }
+
+            public int compareTo(Solution that)
+            {
+                for (int i = 0; i < n; i++)
+                {
+                    int r = pts[0].compareTo(that.pts[0]);
+                    if (r != 0) return r;
+                }
+                return 0;
+            }
+        }
+
+        In in = new In(args[0]);
+        int n = in.readInt();
+
+        StdDraw.setXscale(0, 32768);
+        StdDraw.setYscale(0, 32768);
+
+        Point[] pts = new Point[n];
+        for (int i = 0; i < n; i++)
+        {
+            pts[i] = new Point(in.readInt(), in.readInt());
+        }
+
+        List<Solution> res = new ArrayList<Solution>();
+        Point[] others = new Point[n];
+        for (int i = 0; i < n; i++)
+        {
+            Point ref = pts[i];
+            ref.draw();
+            for (int j = 0; j < n; j++)
+                others[j] = pts[j];
+
+            Arrays.sort(others, ref.SLOPE_ORDER);
+
+            int start = 0;
+            double slope = Double.NEGATIVE_INFINITY;
+            for (int j = 1; j < n; j++)
+            {
+                double sl = ref.slopeTo(others[j]);
+                if (sl == Double.NEGATIVE_INFINITY)
+                    continue;
+
+                if (slope != sl)
+                {
+                    if ((start != 0) && ((j - start) > 2)) {
+                        Solution sol = new Solution(j - start + 1);
+                        sol.add(ref);
+                        for (int k = start; k < j; k++)
+                            sol.add(others[k]);
+                        sol.sort();
+                        if (!res.contains(sol))
+                            res.add(sol);
+                    }
+                    slope = sl;
+                    start = j;
+                }
+
+            }
+            if ((n -  start) > 2) {
+                Solution sol = new Solution(n - start + 1);
+                sol.add(ref);
+                for (int k = start; k < n; k++)
+                    sol.add(others[k]);
+                sol.sort();
+                if (!res.contains(sol))
+                    res.add(sol);
+            }
+        }
+
+        Solution[] sorted = new Solution[res.size()];
+        res.toArray(sorted);
+        Insertion.sort(sorted);
+        for (Solution sol : sorted)
+        {
+            sol.draw();
+            sol.print();
+        }
+        StdDraw.show(0);
+    }
+}
+