Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Correctness: 41/41 tests passed
- Memory: 1/1 tests passed
- Timing: 41/41 tests passed
- Aggregate score: 100.00%*/
- 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.Comparator;
- public class FastCollinearPoints {
- // since HashSets are not permitted as per assignments
- private ArrayList<LineSegment> lineSegments;
- // finds all line segments containing 4 points
- public FastCollinearPoints(Point[] points) {
- checkNull(points);
- checkDuplicates(points);
- lineSegments = new ArrayList<>();
- int n = points.length;
- Point[] copyPoints = points.clone(); // TO AVOID MUTATING THE ARRAY
- for (int i = 0; i < n - 3; i++) {
- Arrays.sort(copyPoints); // resort as order has been modified by subsequent BY_SLOPE_ORDER call
- // for each point we sort the points array by slope order
- Comparator<Point> BY_SLOPE_ORDER = copyPoints[i].slopeOrder();
- Arrays.sort(copyPoints, BY_SLOPE_ORDER);
- // we check if the next 2 points in the slope sorted array have equal slopes with respect to this point
- // this double cursor allows to find segments greater than 4 in length without the costly operation of merging and recomputing some slopes for aligned segments which will end up being too slow
- for (int origine = 0, first = 1, last = 2; last < n; last++) { // thanks AlexJoz
- while (last < n && copyPoints[origine].slopeTo(copyPoints[first]) == copyPoints[origine].slopeTo(copyPoints[last])) {
- last++;
- }
- if (last - first >= 3 && copyPoints[origine].compareTo(copyPoints[first]) < 0) { // to avoid writing duplicates segments
- lineSegments.add(new LineSegment(copyPoints[origine], copyPoints[last - 1]));
- }
- first = last; // search for the next aligned points
- }
- }
- }
- private void checkDuplicates(Point[] points) {
- int n = points.length;
- if (n > 0) {
- Point[] pointsCopy = new Point[n];
- System.arraycopy(points, 0, pointsCopy, 0, n);
- Arrays.sort(pointsCopy);
- // only one pass in this search since array is already sorted
- for (int i = 0; i < n - 1; i++)
- if (pointsCopy[i].compareTo(pointsCopy[i + 1]) == 0)
- throw new IllegalArgumentException(
- pointsCopy[i + 1] + "is a duplicate point !");
- }
- }
- private void checkNull(Point[] points) {
- if (points == null) {
- throw new IllegalArgumentException("in FastCollinear the Point array cannot be null.");
- } else {
- for (Point p : points) {
- if (p == null) {
- throw new IllegalArgumentException(
- "in FastCollinear one point in points is null.");
- }
- }
- }
- }
- // the number of line segments
- public int numberOfSegments() {
- return lineSegments.size();
- }
- // the line segments
- public LineSegment[] segments() {
- LineSegment[] lineSegmentsRes = new LineSegment[numberOfSegments()];
- for (int i = 0; i < numberOfSegments(); i++) {
- lineSegmentsRes[i] = lineSegments.get(i);
- }
- return lineSegmentsRes;
- }
- // FastCollinearPoints sample client - to delete when submitting
- 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);
- StdDraw.setPenColor();
- StdDraw.setPenRadius(0.01);
- for (Point p : points) {
- p.draw();
- }
- StdDraw.show();
- // print and draw the line segments
- FastCollinearPoints collinear = new FastCollinearPoints(points);
- LineSegment[] lineSegments = collinear.segments();
- for (LineSegment segment : lineSegments) {
- if (null != segment) {
- StdOut.println(segment);
- segment.draw();
- }
- }
- StdDraw.show();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement