アルゴリズム

アルゴリズムコース-コリニアポイント-割り当て



Algorithm Course Collinear Point Assignment



理解

平面内の点の中から同一線上にある点を見つけ、同一線上にある点（つまり、線分）の頭と尾に印を付けます。ポイントクラスと同一線上のポイントを見つけるためのクラスを実装する必要があります。アルゴリズムの複雑さはN ^ 4とN ^ 2 * lgNです。



問題分析

詳細については、コードコメントを参照してください



最も難しいのは、勾配でソートされたポイントセットに従って共起ポイントのヘッドとテールを見つけ、それを1回だけ出力する方法です。アルゴリズムのアイデアは、最初に各ポイントの傾きで並べ替え、次に指定されたポイントの傾きで並べ替えることです。同じ勾配のポイントは、共線性を満たすポイントであると同時に、comparetoメソッドを使用して、同一線上のポイントが1回だけ出力されるようにします。

その他

https://www.cnblogs.com/cnu4/articles/3998106.html



リンク

/****************************************************************************** * Compilation: javac Point.java * Execution: java Point * Dependencies: none * * An immutable data type for points in the plane. * For use on Coursera, Algorithms Part I programming assignment. * ******************************************************************************/ import edu.princeton.cs.algs4.StdDraw import java.util.Comparator public class Point implements Comparable { // public static final Comparator By_Slope = new BySlope() private final int x // x-coordinate of this point private final int y // y-coordinate of this point /** * Initializes a new point. * * @param x the x -coordinate of the point * @param y the y -coordinate of the point */ public Point(int x, int y) { /* DO NOT MODIFY */ this.x = x this.y = y } /** * Draws this point to standard draw. */ public void draw() { /* DO NOT MODIFY */ StdDraw.point(x, y) } /** * Draws the line segment between this point and the specified point * to standard draw. * * @param that the other point */ public void drawTo(Point that) { /* DO NOT MODIFY */ StdDraw.line(this.x, this.y, that.x, that.y) } /** * Returns the slope between this point and the specified point. * Formally, if the two points are (x0, y0) and (x1, y1), then the slope * is (y1 - y0) / (x1 - x0). For completeness, the slope is defined to be * +0.0 if the line segment connecting the two points is horizontal * Double.POSITIVE_INFINITY if the line segment is vertical * and Double.NEGATIVE_INFINITY if (x0, y0) and (x1, y1) are equal. * * @param that the other point * @return the slope between this point and the specified point */ public double slopeTo(Point that) { /* YOUR CODE HERE */ if (this.x == that.x && this.y == that.y) { // a point and itself return Double.NEGATIVE_INFINITY } if (this.y == that.y) { // horizontal line return +0.0 } if (this.x == that.x) { // vertical line return Double.POSITIVE_INFINITY } return 1.0 * (that.y - this.y) / (that.x - this.x) } /** * Compares two points by y-coordinate, breaking ties by x-coordinate. * Formally, the invoking point (x0, y0) is less than the argument point * (x1, y1) if and only if either y0 /* ***************************************************************************** * Name: * Date: * Description: **************************************************************************** */ import edu.princeton.cs.algs4.In import edu.princeton.cs.algs4.StdDraw import edu.princeton.cs.algs4.StdOut import java.util.ArrayList import java.util.Arrays import java.util.List public class BruteCollinearPoints { private List lineSegments = new ArrayList() // finds all line segments containing 4 points public BruteCollinearPoints(Point[] points) { if (points == null) { throw new IllegalArgumentException() } Point[] clone = new Point[points.length] int len = 0 for (Point point : points) { if (point == null) { throw new IllegalArgumentException() } else { clone[len] = point len++ } } Arrays.sort(clone) //check if duplicate point for(int i = 0 i /* ***************************************************************************** * Name: * Date: * Description: **************************************************************************** */ import edu.princeton.cs.algs4.In import edu.princeton.cs.algs4.StdDraw import edu.princeton.cs.algs4.StdOut import java.util.ArrayList import java.util.Arrays import java.util.LinkedList import java.util.List public class FastCollinearPoints { private List lineSegments = new ArrayList() // finds all line segments containing 4 or more points public FastCollinearPoints(Point[] points) { if (points == null) { throw new IllegalArgumentException() } Point[] clone = new Point[points.length] int len = 0 // kick null point for (Point point : points) { if (point == null) { throw new IllegalArgumentException() } else { clone[len] = point len++ } } //check duplicate point Arrays.sort(clone) for(int i = 0 i