1 files changed, 92 insertions, 0 deletions
diff --git a/Algorithms/Part-I/3-Collinear/Brute.java b/Algorithms/Part-I/3-Collinear/Brute.java
new file mode 100644
index 0000000..d7eb052
--- /dev/null
+++ b/Algorithms/Part-I/3-Collinear/Brute.java
@@ -0,0 +1,92 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+import java.util.List;
+import java.util.ArrayList;
+
+public class Brute
+{
+
+    public static void main(String[] args)
+    {
+        class Solution implements Comparable<Solution>
+        {
+            private Point[] pts = new Point[4];
+
+            public Solution(Point p, Point q, Point r, Point s)
+            {
+                pts[0] = p;
+                pts[1] = q;
+                pts[2] = r;
+                pts[3] = s;
+                Insertion.sort(pts);
+            }
+
+            public void draw()
+            {
+                pts[0].drawTo(pts[3]);
+            }
+
+            public void print()
+            {
+                System.out.println(pts[0]+" -> "+pts[1]+" -> "+pts[2]+" -> "+pts[3]);
+            }
+
+            public int compareTo(Solution that)
+            {
+                int r = pts[0].compareTo(that.pts[0]);
+                if (r != 0) return r;
+                r = pts[1].compareTo(that.pts[1]);
+                if (r != 0) return r;
+                r = pts[2].compareTo(that.pts[2]);
+                if (r != 0) return r;
+                return pts[3].compareTo(that.pts[3]);
+            }
+        }
+
+        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++)
+        {
+            Point p = new Point(in.readInt(), in.readInt());
+            pts[i] = p;
+            p.draw();
+        }
+
+        List<Solution> res = new ArrayList<Solution>();
+        for (int p = 0; p < n; p++)
+        {
+            for (int q = p+1; q < n; q++)
+            {
+                double sl = pts[p].slopeTo(pts[q]);
+                for (int r = q+1; r < n; r++)
+                {
+                    if (!(sl == pts[p].slopeTo(pts[r])))
+                        continue;
+                    for (int s = r+1; s < n; s++)
+                    {
+                        if (sl == pts[p].slopeTo(pts[s]))
+                        {
+                            res.add(new Solution(pts[p], pts[q], pts[r], pts[s]));
+                        }
+                    }
+                }
+            }
+        }
+
+        Solution[] sorted = new Solution[res.size()];
+        res.toArray(sorted);
+        Insertion.sort(sorted);
+        for (Solution sol : sorted)
+        {
+            sol.draw();
+            sol.print();
+        }
+        StdDraw.show(0);
+    }
+}
+