summaryrefslogtreecommitdiffstats
path: root/Algorithms/Part-I/3-Collinear/Brute.java
diff options
context:
space:
mode:
Diffstat (limited to 'Algorithms/Part-I/3-Collinear/Brute.java')
-rw-r--r--Algorithms/Part-I/3-Collinear/Brute.java92
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);
+ }
+}
+