Algorithms-I : 3-Collinear: first submission, Fast is slow ;)

1 files changed, 122 insertions, 0 deletions

diff --git a/Algorithms/Part-I/3-Collinear/Point.java b/Algorithms/Part-I/3-Collinear/Point.java
new file mode 100644
index 0000000..bd5bbe7
--- /dev/null
+++ b/Algorithms/Part-I/3-Collinear/Point.java
@@ -0,0 +1,122 @@
+/*************************************************************************
+ * Name:
+ * Email:
+ *
+ * Compilation:  javac Point.java
+ * Execution:
+ * Dependencies: StdDraw.java
+ *
+ * Description: An immutable data type for points in the plane.
+ *
+ *************************************************************************/
+
+import java.util.Comparator;
+
+public class Point implements Comparable<Point> {
+
+    // compare points by slope
+    public final Comparator<Point> SLOPE_ORDER = new SlopeOrder();
+
+    private final int x;                              // x coordinate
+    private final int y;                              // y coordinate
+
+    // create the point (x, y)
+    public Point(int x, int y) {
+        /* DO NOT MODIFY */
+        this.x = x;
+        this.y = y;
+    }
+
+    // plot this point to standard drawing
+    public void draw() {
+        /* DO NOT MODIFY */
+        StdDraw.point(x, y);
+    }
+
+    // draw line between this point and that point to standard drawing
+    public void drawTo(Point that) {
+        /* DO NOT MODIFY */
+        StdDraw.line(this.x, this.y, that.x, that.y);
+    }
+
+    // slope between this point and that point
+    public double slopeTo(Point that) {
+        if (this.y == that.y && this.x == that.x) return Double.NEGATIVE_INFINITY;
+
+        double dx = that.x - this.x;
+        if (dx == 0.0) return Double.POSITIVE_INFINITY;
+
+        double dy = that.y - this.y;
+        if (dy == 0.0) return +0;
+
+        return dy / dx;
+    }
+
+    private class SlopeOrder implements Comparator<Point>
+    {
+        public int compare(Point p, Point q)
+        {
+            double sp = slopeTo(p);
+            double sq = slopeTo(q);
+            if (sp < sq) return -1;
+            if (sp > sq) return  1;
+            return 0;
+        }
+    }
+
+    // is this point lexicographically smaller than that one?
+    // comparing y-coordinates and breaking ties by x-coordinates
+    public int compareTo(Point that) {
+        if (this.y < that.y) return -1;
+        if (this.y > that.y) return  1;
+        if (this.x < that.x) return -1;
+        if (this.x > that.x) return  1;
+        return 0;
+    }
+
+    // return string representation of this point
+    public String toString() {
+        /* DO NOT MODIFY */
+        return "(" + x + ", " + y + ")";
+    }
+
+    // unit test
+    public static void main(String[] args) {
+        System.out.println("Point.java asserts");
+        Point p0 = new Point(5, 4);
+
+        Point p1 = new Point(5, 4);
+        Point p2 = new Point(9, 3);
+        Point p3 = new Point(0, 5);
+        Point p4 = new Point(4, 4);
+        Point p5 = new Point(6, 4);
+
+        assert (p0.compareTo(p1) ==  0) : "compareTo p1";
+        assert (p0.compareTo(p2) ==  1) : "compareTo p2";
+        assert (p0.compareTo(p3) == -1) : "compareTo p3";
+        assert (p0.compareTo(p4) ==  1) : "compareTo p4";
+        assert (p0.compareTo(p5) == -1) : "compareTo p5";
+
+        Point[] pts = new Point[8];
+        pts[0] = new Point(-5, 3);
+        pts[1] = new Point(3, 5);
+        pts[2] = new Point(4, 3);
+        pts[3] = new Point(3, 3);
+        pts[4] = new Point(3, 0);
+        pts[5] = new Point(9, 6);
+        pts[6] = new Point(5, 5);
+        pts[7] = new Point(6, 0);
+
+        Point ref = pts[3];
+        System.out.println("REF: "+ref);
+        Selection.sort(pts, ref.SLOPE_ORDER);
+        double t = Double.NEGATIVE_INFINITY;
+        for (Point p : pts)
+        {
+            assert t <= ref.slopeTo(p);
+            System.out.println("  "+p+" "+ref.slopeTo(p));
+            t = ref.slopeTo(p);
+        }
+        System.out.println("SUCCESS");
+    }
+}