算法导论第四版学习——习题三Collinear Points

题目正文：

http://coursera.cs.princeton.edu/algs4/assignments/collinear.html

作业难点：

1、仔细思考会感觉有很多实现方法，但是如果没有适当使用排序，算法时间复杂度就会轻易超过要求。（包括暴力算法）

2、隐含需要实现自己的数据结构用来组织“线”的集合，当然也可以用Stack或者Queue或者LinkedList，但是我个人是自己实现的。

3、由于一条线段只能出现一次，所以有一个去重的问题。（最难）

作业技巧：

1、基本按照题目的先后顺序实现，结合视频学习中的一些知识点就可以把任务串起来，不会无从下手。

2、SlopTo的计算结果和点数组的排列顺序有关吗？A.SlopeTo(B)和B.SlopeTo(A)其实是一样的，合理利用cache防止多次计算。

3、在暴力方法中，引入排序可以解决去重问题。

4、如果去重是通过在结果集合中查找是否存在，就铁定会超过复杂度要求，所以必须在添加结果集之前就能判断。

这里就有一个重要推论：a-b-c-d线段，无论从a开始查找还是从b开始查找，线段最大和最小点都不变为a和d，所以我们只需要找到起始点为线段最小点的线段就可以了，其他线段均抛弃即可

代码参考：

（这是我自己亲测100分的答案，不代表写得最好，请在自己实在完成不了的时候再看，不然的话做这个题目的意义一点都没有）

  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 points
101      */
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 point
112      */
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 }

Point

  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 = new LineSegment(clone[i],
 49                                         clone[n]);
 50                                 last = newNode;
 51                             } else {
 52                                 last = new Node();
 53                                 last.value = 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 segments
107         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 }

BruteCollinearPoints

  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 = new LineSegment(a, b);
104             last = newNode;
105         } else {
106             last = new Node();
107             last.value = new LineSegment(a, b);
108         }
109         lineNumber++;
110     }
111 
112     public int numberOfSegments() // the number of line segments
113      {
114         return lineNumber;
115     }
116 
117     public LineSegment[] segments() // the line segments
118      {
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 file
132         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 points
143         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 segments
154         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 }

FastCollinearPoints