1 import edu.princeton.cs.algs4.StdDraw;  2   3 /******************************************************************************  4  *  Compilation:  javac Point.java  5  *  Execution:    java Point  6  *  Dependencies: none  7  *  8  *  An immutable data type for points in the plane.  9  *  For use on Coursera, Algorithms Part I programming assignment. 10  * 11  ******************************************************************************/ 12 import java.util.Comparator; 13  14  15 public class Point implements Comparable<Point> { 16     private final int x; // x-coordinate of this point 17     private final int y; // y-coordinate of this point 18  19     /** 20      * Initializes a new point. 21      * 22      * @param  x the <em>x</em>-coordinate of the point 23      * @param  y the <em>y</em>-coordinate of the point 24      */ 25     public Point(int x, int y) { 26         /* DO NOT MODIFY */ 27         this.x = x; 28         this.y = y; 29     } 30  31     /** 32      * Draws this point to standard draw. 33      */ 34     public void draw() { 35         /* DO NOT MODIFY */ 36         StdDraw.point(x, y); 37     } 38  39     /** 40      * Draws the line segment between this point and the specified point 41      * to standard draw. 42      * 43      * @param that the other point 44      */ 45     public void drawTo(Point that) { 46         /* DO NOT MODIFY */ 47         StdDraw.line(this.x, this.y, that.x, that.y); 48     } 49  50     /** 51      * Returns the slope between this point and the specified point. 52      * Formally, if the two points are (x0, y0) and (x1, y1), then the slope 53      * is (y1 - y0) / (x1 - x0). For completeness, the slope is defined to be 54      * +0.0 if the line segment connecting the two points is horizontal; 55      * Double.POSITIVE_INFINITY if the line segment is vertical; 56      * and Double.NEGATIVE_INFINITY if (x0, y0) and (x1, y1) are equal. 57      * 58      * @param  that the other point 59      * @return the slope between this point and the specified point 60      */ 61     public double slopeTo(Point that) { 62         if ((this.x == that.x) && (this.y == that.y)) { 63             return Double.NEGATIVE_INFINITY; 64         } else if (this.x == that.x) { 65             return Double.POSITIVE_INFINITY; 66         } else if (this.y == that.y) { 67             return 0; 68         } else { 69             return (that.y - this.y) / (double) (that.x - this.x); 70         } 71     } 72  73     /** 74      * Compares two points by y-coordinate, breaking ties by x-coordinate. 75      * Formally, the invoking point (x0, y0) is less than the argument point 76      * (x1, y1) if and only if either y0 < y1 or if y0 = y1 and x0 < x1. 77      * 78      * @param  that the other point 79      * @return the value <tt>0</tt> if this point is equal to the argument 80      *         point (x0 = x1 and y0 = y1); 81      *         a negative integer if this point is less than the argument 82      *         point; and a positive integer if this point is greater than the 83      *         argument point 84      */ 85     public int compareTo(Point that) { 86         if ((this.x == that.x) && (this.y == that.y)) { 87             return 0; 88         } else if ((that.y > this.y) || 89                 ((that.y == this.y) && (that.x > this.x))) { 90             return -1; 91         } else { 92             return 1; 93         } 94     } 95  96     /** 97      * Compares two points by the slope they make with this point. 98      * The slope is defined as in the slopeTo() method. 99      *100      * @return the Comparator that defines this ordering on points101      */102     public Comparator<Point> slopeOrder() {103         return new SlopeOrder(this);104     }105 106     /**107      * Returns a string representation of this point.108      * This method is provide for debugging;109      * your program should not rely on the format of the string representation.110      *111      * @return a string representation of this point112      */113     public String toString() {114         /* DO NOT MODIFY */115         return "(" + x + ", " + y + ")";116     }117 118     /**119      * Unit tests the Point data type.120      */121     public static void main(String[] args) {122         /* YOUR CODE HERE */123     }124 125     private class SlopeOrder implements Comparator<Point> {126         private Point p0;127 128         public SlopeOrder(Point invokePoint) {129             p0 = invokePoint;130         }131 132         public int compare(Point p1, Point p2) {133             double d01 = p0.slopeTo(p1);134             double d02 = p0.slopeTo(p2);135 136             if (d01 < d02) {137                 return -1;138             } else if (d01 > d02) {139                 return 1;140             } else {141                 return 0;142             }143         }144     }145 }

  1 import edu.princeton.cs.algs4.In;  2 import edu.princeton.cs.algs4.StdDraw;  3 import edu.princeton.cs.algs4.StdOut;  4 import java.util.Arrays;  5   6 public class BruteCollinearPoints {  7     private int lineNumber;  8     private Node last;  9  10     public BruteCollinearPoints(Point[] points) // finds all line segments containing 4 points 11      { 12        13         if (points == null) { 14             throw new NullPointerException(); 15         } 16  17         lineNumber = 0; 18  19         int num = points.length; 20  21         Point[] clone = new Point[num]; 22          23         for (int i = 0; i < num; i++) { 24             if (points[i] == null) { 25                 throw new NullPointerException(); 26             } 27  28             for (int j = i + 1; j < num; j++) { 29                 if (points[i].compareTo(points[j]) == 0) { 30                     throw new IllegalArgumentException(); 31                 } 32             } 33             clone[i] = points[i]; 34         } 35         Arrays.sort(clone); 36         for (int i = 0; i < num; i++) { 37             for (int j = i+1; j < num; j++) { 38                 for (int m = j+1; m < num; m++) { 39                     for (int n = m+1; n < num; n++) { 40                         double d01 = clone[i].slopeTo(clone[j]); 41                         double d02 = clone[j].slopeTo(clone[m]); 42                         double d03 = clone[m].slopeTo(clone[n]); 43  44                         if (d01 == d02 && d02 == d03)  { 45                             if (last != null) { 46                                 Node newNode = new Node(); 47                                 newNode.prev = last; 48                                 newNode.value = http://www.mamicode.com/new LineSegment(clone[i], 49                                         clone[n]); 50                                 last = newNode; 51                             } else { 52                                 last = new Node(); 53                                 last.value = http://www.mamicode.com/new LineSegment(clone[i], 54                                         clone[n]); 55                             } 56  57                             lineNumber++; 58                         } 59                     } 60                 } 61             } 62         } 63     } 64  65     public int numberOfSegments() // the number of line segments 66      { 67         return lineNumber; 68     } 69  70     public LineSegment[] segments() // the line segments 71      { 72         LineSegment[] lines = new LineSegment[lineNumber]; 73         Node current = last; 74  75         for (int i = 0; i < lineNumber; i++) { 76             lines[i] = current.value; 77             current = current.prev; 78         } 79  80         return lines; 81     } 82  83     public static void main(String[] args) { 84         // read the n points from a file 85         In in = new In(args[0]); 86         int n = in.readInt(); 87         Point[] points = new Point[n]; 88  89         for (int i = 0; i < n; i++) { 90             int x = in.readInt(); 91             int y = in.readInt(); 92             points[i] = new Point(x, y); 93         } 94  95         // draw the points 96         StdDraw.enableDoubleBuffering(); 97         StdDraw.setXscale(0, 32768); 98         StdDraw.setYscale(0, 32768); 99 100         for (Point p : points) {101             p.draw();102         }103 104         StdDraw.show();105 106         // print and draw the line segments107         BruteCollinearPoints collinear = new BruteCollinearPoints(points);108 109         for (LineSegment segment : collinear.segments()) {110             StdOut.println(segment);111             segment.draw();112         }113 114         StdDraw.show();115     }116 117     private class Node {118         private LineSegment value;119         private Node prev;120     }121 }

  1 import edu.princeton.cs.algs4.In;  2 import edu.princeton.cs.algs4.StdDraw;  3 import edu.princeton.cs.algs4.StdOut;  4   5 import java.util.Arrays;  6   7 public class FastCollinearPoints {  8     private int lineNumber;  9     private Node last; 10  11     public FastCollinearPoints(Point[] points) // finds all line segments containing 4 or more points 12      { 13         if (points == null) { 14             throw new NullPointerException(); 15         } 16  17         lineNumber = 0; 18  19         int num = points.length; 20         Point[] clone = new Point[num]; 21  22         for (int i = 0; i < num; i++) { 23             if (points[i] == null) { 24                 throw new NullPointerException(); 25             } 26  27             for (int j = i + 1; j < num; j++) { 28                 if (points[i].compareTo(points[j]) == 0) { 29                     throw new IllegalArgumentException(); 30                 } 31             } 32             clone[i] = points[i]; 33         } 34         Arrays.sort(clone); 35          36         if (num < 4) { 37             return; 38         } 39  40         for (int i = 0; i < num - 1; i++) { 41             int tempPointsNum = 0; 42             Point[] tempPoints = new Point[num - 1]; 43  44             for (int j = 0; j < num; j++) { 45                 if (i != j) tempPoints[tempPointsNum++] = clone[j]; 46             } 47  48             Arrays.sort(tempPoints, clone[i].slopeOrder()); 49  50             int count = 0; 51             Point min = null; 52             Point max = null; 53              54             for (int j = 0; j < (tempPointsNum - 1); j++) { 55                 if (clone[i].slopeTo(tempPoints[j]) == clone[i].slopeTo( 56                             tempPoints[j + 1])) { 57                     if (min == null) { 58                         if (clone[i].compareTo(tempPoints[j]) > 0) { 59                             max = clone[i]; 60                             min = tempPoints[j]; 61                         } else { 62                             max = tempPoints[j]; 63                             min = clone[i]; 64                         } 65                     } 66  67                     if (min.compareTo(tempPoints[j + 1]) > 0) { 68                         min = tempPoints[j + 1]; 69                     } 70  71                     if (max.compareTo(tempPoints[j + 1]) < 0) { 72                         max = tempPoints[j + 1]; 73                     } 74  75                     count++; 76  77                     if (j == (tempPointsNum - 2)) { 78                         if (count >= 2 && clone[i].compareTo(min) == 0) { 79                             addLine(min, max); 80                         } 81  82                         count = 0; 83                         min = null; 84                         max = null; 85                     } 86                 } else { 87                     if (count >= 2 && clone[i].compareTo(min) == 0) { 88                         addLine(min, max); 89                     } 90  91                     count = 0; 92                     min = null; 93                     max = null; 94                 } 95             } 96         } 97     } 98  99     private void addLine(Point a, Point b) {100         if (last != null) {101             Node newNode = new Node();102             newNode.prev = last;103             newNode.value = http://www.mamicode.com/new LineSegment(a, b);104             last = newNode;105         } else {106             last = new Node();107             last.value = http://www.mamicode.com/new LineSegment(a, b);108         }109         lineNumber++;110     }111 112     public int numberOfSegments() // the number of line segments113      {114         return lineNumber;115     }116 117     public LineSegment[] segments() // the line segments118      {119         LineSegment[] lines = new LineSegment[lineNumber];120         Node current = last;121 122         for (int i = 0; i < lineNumber; i++) {123             lines[i] = current.value;124             current = current.prev;125         }126 127         return lines;128     }129 130     public static void main(String[] args) {131         // read the n points from a file132         In in = new In(args[0]);133         int n = in.readInt();134         Point[] points = new Point[n];135 136         for (int i = 0; i < n; i++) {137             int x = in.readInt();138             int y = in.readInt();139             points[i] = new Point(x, y);140         }141 142         // draw the points143         StdDraw.enableDoubleBuffering();144         StdDraw.setXscale(0, 32768);145         StdDraw.setYscale(0, 32768);146 147         for (Point p : points) {148             p.draw();149         }150 151         StdDraw.show();152 153         // print and draw the line segments154         FastCollinearPoints collinear = new FastCollinearPoints(points);155 156         for (LineSegment segment : collinear.segments()) {157             StdOut.println(segment);158             segment.draw();159         }160 161         StdDraw.show();162     }163 164     private class Node {165         private LineSegment value;166         private Node prev;167     }168 }