Visits: 336

Princeton Algotithms Collinear Points

普林斯顿大学算法课第 3 次作业“共线点”。

作业要求： https://coursera.cs.princeton.edu/algs4/assignments/collinear/specification.php

虽然本次作业给出了暴力方法和快速方法，但是不要以为就能拿到很高的分数。

同样地，想要通过，非常简单，只要答案正确就行了，很容易通过。

但是想要拿到高分，还是不容易的。

以下代码获得 100 分，其中需要注意的点我罗列一下，具体可以看代码理解。

注意这里必须返回正 0，否则 0 带有正负号，会使得平行于 x 轴的排序出错。例如 (0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5) 以 (1, 5) 为排序时结果是 (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (0, 5)，(0, 5) 到最后了。因此不能直接一减、一除，那样的 0 是有正负号的。

事实上这一点，在 API 文档中已经提示地很清楚了。

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.

所以进入构造函数以后，先无脑做 copy。

Stores a reference to an externally mutable object in the instance variable ‘points’, exposing the internal representation of the class.

Instead, create a defensive copy of the object referenced by the parameter variable ‘points’ and store that copy in the instance variable ‘points’.

check that data type is immutable by testing whether each method returns the same value, regardless of any intervening operations

Let’s say you have 5 points in their natural order a, b, c, d, e. When you have b as the anchor and sort the remaining points by slopeOrder, you want points with the same slope to appear in their natural order (i.e. … a, c, d, e, …).

To avoid adding the subsegment (b, c, d, e), whenever you start seeing a new slope (i.e. at a), you just need to check if b is less than a in terms of natural order – if it is not, it means b is not the first point in that segment, then you know you don’t need to add it.

import java.util.ArrayList;
import java.util.Arrays;

public class BruteCollinearPoints {
    private final Point[] points;
    private final LineSegment[] cached;

    public BruteCollinearPoints(Point[] points) {
        if (points == null) {
            throw new IllegalArgumentException();
        }
        // Points array passsed to the constructor can be changed by some other parts of the code while construction is still in progress.
        this.points = Arrays.copyOf(points, points.length);
        for (Point point : this.points) {
            if (point == null) {
                throw new IllegalArgumentException();
            }
        }
        Arrays.sort(this.points);
        for (int i = 0; i < this.points.length; i++) {
            if (i > 0 && Double.compare(this.points[i].slopeTo(this.points[i - 1]), Double.NEGATIVE_INFINITY) == 0) {
                throw new IllegalArgumentException();
            }
        }
        // Stores a reference to an externally mutable object in the instance variable 'points', exposing the internal representation of the class.
        // Instead, create a defensive copy of the object referenced by the parameter variable 'points' and store that copy in the instance variable 'points'.
        cached = cache();
    }

    private LineSegment[] cache() {
        ArrayList<LineSegment> list = new ArrayList<>();
        int n = points.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int m = k + 1; m < n; m++) {
                        Point p = points[i];
                        Point q = points[j];
                        Point r = points[k];
                        Point s = points[m];
                        double slope1 = p.slopeTo(q);
                        double slope2 = p.slopeTo(r);
                        double slope3 = p.slopeTo(s);
                        if (Double.compare(slope1, slope2) == 0 && Double.compare(slope2, slope3) == 0) {
                            list.add(new LineSegment(p, s));
                        }
                    }
                }
            }
        }
        LineSegment[] segments = new LineSegment[list.size()];
        return list.toArray(segments);
    }

    public int numberOfSegments() {
        return cached.length;
    }

    public LineSegment[] segments() {
        // check that data type is immutable by testing whether each method
        // returns the same value, regardless of any intervening operations
        return Arrays.copyOf(cached, cached.length);
    }
}

/*************************************************************************
 *  Compilation:  javac LineSegment.java
 *  Execution:    none
 *  Dependencies: Point.java
 *
 *  An immutable data type for Line segments in the plane.
 *  For use on Coursera, Algorithms Part I programming assignment.
 *
 *  DO NOT MODIFY THIS CODE.
 *
 *************************************************************************/

public class LineSegment {
    private final Point p;   // one endpoint of this line segment
    private final Point q;   // the other endpoint of this line segment

    /**
     * Initializes a new line segment.
     *
     * @param  p one endpoint
     * @param  q the other endpoint
     * @throws NullPointerException if either <tt>p</tt> or <tt>q</tt>
     *         is <tt>null</tt>
     */
    public LineSegment(Point p, Point q) {
        if (p == null || q == null) {
            throw new NullPointerException("argument is null");
        }
        this.p = p;
        this.q = q;
    }

    
    /**
     * Draws this line segment to standard draw.
     */
    public void draw() {
        p.drawTo(q);
    }

    /**
     * Returns a string representation of this line segment
     * This method is provide for debugging;
     * your program should not rely on the format of the string representation.
     *
     * @return a string representation of this line segment
     */
    public String toString() {
        return p + " -> " + q;
    }

    /**
     * Throws an exception if called. The hashCode() method is not supported because
     * hashing has not yet been introduced in this course. Moreover, hashing does not
     * typically lead to good *worst-case* performance guarantees, as required on this
     * assignment.
     *
     * @throws UnsupportedOperationException if called
     */
    public int hashCode() {
        throw new UnsupportedOperationException();
    }

}

import java.util.ArrayList;
import java.util.Arrays;

public class FastCollinearPoints {
    private final Point[] points;
    private final LineSegment[] cached;

    public FastCollinearPoints(Point[] points) {
        if (points == null) {
            throw new IllegalArgumentException();
        }
        // Points array passsed to the constructor can be changed by some other parts of the code while construction is still in progress.
        this.points = Arrays.copyOf(points, points.length);
        for (Point point : this.points) {
            if (point == null) {
                throw new IllegalArgumentException();
            }
        }
        Arrays.sort(this.points);
        for (int i = 0; i < this.points.length; i++) {
            if (i > 0 && Double.compare(this.points[i].slopeTo(this.points[i - 1]), Double.NEGATIVE_INFINITY) == 0) {
                throw new IllegalArgumentException();
            }
        }
        // Stores a reference to an externally mutable object in the instance variable 'points', exposing the internal representation of the class.
        // Instead, create a defensive copy of the object referenced by the parameter variable 'points' and store that copy in the instance variable 'points'.
        cached = cache();
    }

    public int numberOfSegments() {
        return cached.length;
    }

    public LineSegment[] segments() {
        // check that data type is immutable by testing whether each method
        // returns the same value, regardless of any intervening operations
        return Arrays.copyOf(cached, cached.length);
    }

    private LineSegment[] cache() {
        ArrayList<LineSegment> list = new ArrayList<>();
        Arrays.sort(points);
        for (Point p: points) {
            Point[] pp = Arrays.copyOf(points, points.length);
            if (pp.length < 4) {
                continue;
            }
            Arrays.sort(pp, p.slopeOrder());
            int begin = 1;
            int end = 1;
            double last = p.slopeTo(pp[end]);
            for (int j = 2; j < pp.length; j++) {
                double slope = p.slopeTo(pp[j]);
                if (Double.compare(last, slope) != 0) {
                    if (end - begin >= 2) {
                        // end - begin + 1 有 3 个以上了，加上 p（即pp[0]） 就至少有 4 个了
                        if (p.compareTo(pp[begin]) < 0) {
                            // 去掉子线段
                            /*
                            Let's say you have 5 points in their natural order a, b, c, d, e.
                            When you have b as the anchor and sort the remaining points by slopeOrder, you want points with the same slope to appear in their natural order (i.e. ... a, c, d, e, ...).
                            To avoid adding the subsegment (b, c, d, e), whenever you start seeing a new slope (i.e. at a), you just need to check if b is less than a in terms of natural order
                            - if it is not, it means b is not the first point in that segment, then you know you don't need to add it.
                             */
                            list.add(new LineSegment(p, pp[end]));
                        }
                    }
                    last = slope;
                    begin = j;
                }
                end = j;
            }
            if (end - begin >= 2) {
                if (p.compareTo(pp[begin]) < 0) {
                    list.add(new LineSegment(p, pp[end]));
                }
            }
        }
        LineSegment[] segments = new LineSegment[list.size()];
        return list.toArray(segments);
    }
}

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;

public class Client {
    public static void main(String[] args) {

        // read the n points from a file
        In in = new In(args[0]);
        int n = in.readInt();
        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            int x = in.readInt();
            int y = in.readInt();
            points[i] = new Point(x, y);
        }

        // draw the points
        StdDraw.enableDoubleBuffering();
        StdDraw.setXscale(0, 32768);
        StdDraw.setYscale(0, 32768);
        for (Point p : points) {
            p.draw();
        }
        StdDraw.show();

        // print and draw the line segments
        FastCollinearPoints collinear = new FastCollinearPoints(points);
        for (LineSegment segment : collinear.segments()) {
            StdOut.println(segment);
            segment.draw();
        }
        points[0] = new Point(0, 0);
        for (LineSegment segment : collinear.segments()) {
            StdOut.println(segment);
            segment.draw();
        }
        StdDraw.show();
    }
}

/******************************************************************************
 *  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 java.util.Arrays;
import java.util.Comparator;

import edu.princeton.cs.algs4.StdDraw;

public class Point implements Comparable<Point> {

    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 <em>x</em>-coordinate of the point
     * @param y the <em>y</em>-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 (x == that.x && y == that.y) {
            return Double.NEGATIVE_INFINITY;
        } else if (x == that.x) {
            return Double.POSITIVE_INFINITY;
        } else if (y == that.y) {
            return 0;
            // 注意这里必须返回正 0，否则 0 带有正负号，会使得平行于 x 轴的排序出错
            // 例如 (0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5) 以 (1, 5) 为排序时结果是
            // (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (0, 5)
            // (0, 5) 到最后了
        } else {
            return (double) (y - that.y) / (x - that.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 < y1 or if y0 = y1 and x0 < x1.
     *
     * @param that the other point
     * @return the value <tt>0</tt> if this point is equal to the argument
     * point (x0 = x1 and y0 = y1);
     * a negative integer if this point is less than the argument
     * point; and a positive integer if this point is greater than the
     * argument point
     */
    @Override
    public int compareTo(Point that) {
        /* YOUR CODE HERE */
        if (y != that.y) {
            return Integer.compare(y, that.y);
        } else {
            return Integer.compare(x, that.x);
        }
    }

    /**
     * Compares two points by the slope they make with this point.
     * The slope is defined as in the slopeTo() method.
     *
     * @return the Comparator that defines this ordering on points
     */
    public Comparator<Point> slopeOrder() {
        /* YOUR CODE HERE */
        return new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return Double.compare(slopeTo(o1), slopeTo(o2));
            }
        };
    }


    /**
     * Returns a string representation of this point.
     * This method is provide for debugging;
     * your program should not rely on the format of the string representation.
     *
     * @return a string representation of this point
     */
    @Override
    public String toString() {
        /* DO NOT MODIFY */
        return "(" + x + ", " + y + ")";
    }

    /**
     * Unit tests the Point data type.
     */
    public static void main(String[] args) {
        /* YOUR CODE HERE */
        Point p1 = new Point(0, 0);
        Point p2 = new Point(1, 1);
        System.out.println(p1.compareTo(p2));
        System.out.println(p1.slopeTo(p2));
        Point[] pp = new Point[3];
        pp[0] = new Point(2, 1);
        pp[1] = new Point(0, 0);
        pp[2] = new Point(1, 1);
        Arrays.sort(pp, pp[1].slopeOrder());
        System.out.println(Arrays.toString(pp));
    }
}