Coursera Algorithms Programming Assignment 3: Pattern Recognition （100分）

题目原文详见http://coursera.cs.princeton.edu/algs4/assignments/collinear.html

程序的主要目的是寻找n个points中的line segment，line segment的要求就是包含不少于4个点。

作业包含三部分程序实现：

一、Point

compareTo()用来比较本节点this与其他节点that的大小：假如this节点坐标(x0, y0)，that节点坐标(x1, y1)，只有y0 < y1或(y0==y1 && x0<x1)的时候this < that

slopeTo()用来计算that节点到本节点this的斜率，计算方法为(y₁ − y₀) / (x₁ − x₀)，特别注意的是，x0 != x1 && y0==y1时，slople为0，x0==x1 && y0!=y1时，slople应为positive infinity，x0==x1 && y0==y1时，slope应为negative infinity，

slopeOrder()用来返回比较器，这个比较器的参照点是本节点p0(x0, y0)，如果两个待比较节点分别是p1(x1, y1)和p2(x2, y2)，此比较器的设计要求是当p1相对于p0的斜率大于p2相对于p0的斜率时，p1>p2。比较器主要在排序方法中使用

 1 import java.util.Comparator; 2 import edu.princeton.cs.algs4.StdDraw; 3  4 public class Point implements Comparable<Point> { 5  6   private final int x; // x-coordinate of this point 7   private final int y; // y-coordinate of this point 8  9   /** 10    * Initializes a new point. 11    * 12    * @param x 13    *      the <em>x</em>-coordinate of the point 14    * @param y 15    *      the <em>y</em>-coordinate of the point 16   */ 17   public Point(int x, int y) { 18     /* DO NOT MODIFY */ 19     this.x = x; 20     this.y = y; 21   } 22  23   /** 24    * Draws this point to standard draw. 25   */ 26   public void draw() { 27     /* DO NOT MODIFY */ 28     StdDraw.point(x, y); 29   } 30  31   /** 32    * Draws the line segment between this point and the specified point to 33    * standard draw. 34    * 35    * @param that 36    *      the other point 37   */ 38   public void drawTo(Point that) { 39     /* DO NOT MODIFY */ 40     StdDraw.line(this.x, this.y, that.x, that.y); 41   } 42  43   /** 44    * Returns the slope between this point and the specified point. Formally, 45    * if the two points are (x0, y0) and (x1, y1), then the slope is (y1 - y0) 46    * / (x1 - x0). For completeness, the slope is defined to be +0.0 if the 47    * line segment connecting the two points is horizontal; 48    * Double.POSITIVE_INFINITY if the line segment is vertical; and 49    * Double.NEGATIVE_INFINITY if (x0, y0) and (x1, y1) are equal. 50    * 51    * @param that 52    *      the other point 53    * @return the slope between this point and the specified point 54   */ 55   public double slopeTo(Point that) { 56     /* YOUR CODE HERE */ 57     int x0 = this.x; 58     int y0 = this.y; 59     int x1 = that.x; 60     int y1 = that.y; 61     if (x0 == x1 && y0 == y1) 62       return Double.NEGATIVE_INFINITY; 63     else if (x0 == x1) 64       return Double.POSITIVE_INFINITY; 65     else if (y0 == y1) 66       return +0.0; 67     else 68       return (y1 - y0) / (double)(x1 - x0); 69   } 70  71   /** 72    * Compares two points by y-coordinate, breaking ties by x-coordinate. 73    * Formally, the invoking point (x0, y0) is less than the argument point 74    * (x1, y1) if and only if either y0 < y1 or if y0 = y1 and x0 < x1. 75    * 76    * @param that 77    *      the other point 78    * @return the value <tt>0</tt> if this point is equal to the argument point 79    *     (x0 = x1 and y0 = y1); a negative integer if this point is less 80    *     than the argument point; and a positive integer if this point is 81    *     greater than the argument point 82   */ 83   public int compareTo(Point that) { 84     /* YOUR CODE HERE */ 85     int x0 = this.x; 86     int y0 = this.y; 87     int x1 = that.x; 88     int y1 = that.y; 89     if (y0 == y1) { 90       if (x0 == x1) 91         return 0; 92       else if (x0 > x1) 93         return 1; 94       else 95         return -1; 96     } else if (y0 > y1) 97       return 1; 98     else 99       return -1;100   }101 102   /**103    * Compares two points by the slope they make with this point. The slope is104    * defined as in the slopeTo() method.105    *106    * @return the Comparator that defines this ordering on points107   */108   public Comparator<Point> slopeOrder() {109     /* YOUR CODE HERE */110     return new SlopeOrder(this);111   }112   /**113    * 此comparator提供两个点关于参照点的比较方法，主要供排序方法使用114    * invokePoint就是参照点，两个待比较的Point的大小，这就是排序方法中要用的排序依据115    * @author evasean www.cnblogs.com/evasean/116    *117   */118   private class SlopeOrder implements Comparator<Point>{119     private final Point p0;120     public SlopeOrder(Point invokePoint){121       this.p0 = invokePoint;122     }123     @Override124     public int compare(Point o1, Point o2) {125       // TODO Auto-generated method stub126       double slope1 = p0.slopeTo(o1);127       double slope2 = p0.slopeTo(o2);128       return Double.compare(slope1, slope2); //double不推荐用==直接比大小，采用这种方式比较好129     }130   }131 132   /**133    * Returns a string representation of this point. This method is provide for134    * debugging; your program should not rely on the format of the string135    * representation.136    *137    * @return a string representation of this point138   */139   public String toString() {140     /* DO NOT MODIFY */141     return "(" + x + ", " + y + ")";142   }143 144   /**145    * Unit tests the Point data type.146   */147   public static void main(String[] args) {148     /* YOUR CODE HERE */149     Point p1 = new Point(0, 0);150     Point p2 = new Point(1, 1);151     System.out.println("p1.compareTo(p2)=" + p1.compareTo(p2));152     System.out.println("p1.slopeTo(p2)=" + p1.slopeTo(p2));153     Point p3 = new Point(0, 4);154     System.out.println("p1.slopeTo(p3)=" + p1.slopeTo(p3));155     Point p4 = new Point(4, 4);156     System.out.println("p3.compareTo(p4)=" + p3.compareTo(p4));157     System.out.println("p3.slopeTo(p4)=" + p3.slopeTo(p4));158     Point p5 = new Point(0, 0);159     System.out.println("p1.slopeTo(p5)=" + p1.slopeTo(p5));160   }161 }

海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com

原标题：Coursera Algorithms Programming Assignment 3: Pattern Recognition （100分）

关键词：