Algorithms-I : 3-Collinear: major computation speed up

1 files changed, 84 insertions, 88 deletions

diff --git a/Algorithms/Part-I/3-Collinear/Fast.java b/Algorithms/Part-I/3-Collinear/Fast.java
index 2640d65..5d6ad48 100644
--- a/Algorithms/Part-I/3-Collinear/Fast.java
+++ b/Algorithms/Part-I/3-Collinear/Fast.java
@@ -7,94 +7,78 @@ import java.util.Arrays;
 public class Fast
 {
 
-    public static void main(String[] args)
+    static class Segment
     {
-        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;
-            }
+        private Point[] pts;
 
-            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)
+        public Segment(Point ref, Point[] origin, int start, int n)
+        {
+            this.pts = new Point[n];
+            int i = 0;
+            int j = start;
+            boolean inserted = false;
+            while (i < (n - 1))
             {
-                for (int i = 0; i < n; i++)
+                if (!inserted && (ref.compareTo(origin[j]) < 0))
                 {
-                    int r = pts[0].compareTo(that.pts[0]);
-                    if (r != 0) return r;
+                    pts[i++] = ref;
+                    pts[i] = origin[j++];
+                    inserted = true;
                 }
-                return 0;
+                else
+                    pts[i] = origin[j++];
+                i++;
             }
+            if (!inserted)
+                pts[n - 1] = ref;
+            else
+                pts[n - 1] = origin[start + n - 2];
         }
 
-        In in = new In(args[0]);
-        int n = in.readInt();
+        public boolean equals(Object other)
+        {
+            if (other == this) return true;
+            if (other == null) return false;
+            if (other.getClass() != this.getClass()) return false;
+            Segment s = (Segment) other;
+            if ((pts[0].compareTo(s.pts[0]) == 0) || (pts[pts.length - 1].compareTo(s.pts[s.pts.length - 1]) == 0))
+                    return true;
+            return false;
+        }
 
-        StdDraw.setXscale(0, 32768);
-        StdDraw.setYscale(0, 32768);
+        public void draw()
+        {
+            pts[0].drawTo(pts[pts.length-1]);
+        }
 
-        Point[] pts = new Point[n];
-        for (int i = 0; i < n; i++)
+        public void print()
         {
-            pts[i] = new Point(in.readInt(), in.readInt());
+            String out = "";
+            for (Point p : pts)
+                out += p+" -> ";
+            StdOut.println(out.substring(0, (out.length() - 4)));
         }
+    }
 
-        List<Solution> res = new ArrayList<Solution>();
-        Point[] others = new Point[n];
-        for (int i = 0; i < n; i++)
+    static List<Segment> solve(Point[] pts, int N)
+    {
+        List<Segment> segments = new ArrayList<Segment>();
+        for (int i = 0; i < N - 1; i++)
         {
+            int n = N - i - 1;
             Point ref = pts[i];
+            Point[] others = new Point[n];
+
             ref.draw();
-            for (int j = 0; j < n; j++)
-                others[j] = pts[j];
+
+            for (int j = 0, k = i + 1; j < n; j++, k++)
+                others[j] = pts[k];
 
             Arrays.sort(others, ref.SLOPE_ORDER);
 
-            int start = 0;
+            int start = -1;
             double slope = Double.NEGATIVE_INFINITY;
-            for (int j = 1; j < n; j++)
+            for (int j = 0; j < n; j++)
             {
                 double sl = ref.slopeTo(others[j]);
                 if (sl == Double.NEGATIVE_INFINITY)
@@ -102,39 +86,51 @@ public class Fast
 
                 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);
+                    if ((start != -1) && ((j - start) > 2))
+                    {
+                        Segment seg = new Segment(ref, others, start, (j - start + 1));
+                        if (!segments.contains(seg))
+                            segments.add(seg);
                     }
                     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);
+            if ((n -  start) > 2)
+            {
+                Segment seg = new Segment(ref, others, start, (n - start + 1));
+                if (!segments.contains(seg))
+                    segments.add(seg);
             }
         }
+        return segments;
+    }
+
+    public static void main(String[] args)
+    {
+        In in = new In(args[0]);
+        int n = in.readInt();
+
+        StdDraw.setXscale(0, 32768);
+        StdDraw.setYscale(0, 32768);
+        StdDraw.show(0);
+
+        Point[] pts = new Point[n];
+        for (int i = 0; i < n; i++)
+        {
+            pts[i] = new Point(in.readInt(), in.readInt());
+        }
+
+        // Stopwatch w = new Stopwatch();
 
-        Solution[] sorted = new Solution[res.size()];
-        res.toArray(sorted);
-        Insertion.sort(sorted);
-        for (Solution sol : sorted)
+        for (Segment sol : solve(pts, n))
         {
             sol.draw();
             sol.print();
         }
+
+        // StdOut.printf("Time: %f\n\n", w.elapsedTime());
         StdDraw.show(0);
     }
 }