diff options
| -rw-r--r-- | Algorithms/Part-I/3-Collinear/Fast.java | 140 | ||||
| -rw-r--r-- | Algorithms/Part-I/3-Collinear/Point.java | 1 |
2 files changed, 62 insertions, 79 deletions
diff --git a/Algorithms/Part-I/3-Collinear/Fast.java b/Algorithms/Part-I/3-Collinear/Fast.java index 07130a6..60b0d25 100644 --- a/Algorithms/Part-I/3-Collinear/Fast.java +++ b/Algorithms/Part-I/3-Collinear/Fast.java @@ -3,112 +3,100 @@ import java.util.List; import java.util.ArrayList; import java.util.Arrays; +import java.util.HashMap; +import java.util.HashSet; public class Fast { - - private static class Segment + private int N; + private Point ref; + private Point[] pts; + // reused each iteration + private Point[] work; + private List<Point[]> segments; + // for each slope, the last point must be unique, + // the longest segment is the first to arise + // multiple segment for 1 slope is possible + private HashMap<Double, HashSet<Point>> slopes; + + private void addSegment(double sl, int start, int end) { - private Point[] pts; - - public Segment(Point ref, Point[] origin, int start, int n) + // if this solpe is not in the hash yet, + // or the last point is not in the set yet + HashSet slopePoints = slopes.get(sl); + Point last = work[end - 1]; + if ((slopePoints == null) || !slopePoints.contains(last)) { - this.pts = new Point[n]; - int i = 0; - int j = start; - boolean inserted = false; - while (i < (n - 1)) + Point[] segment = new Point[end - start + 1]; + segment[0] = ref; + for (int k = start, l = 1; k < end; k++, l++) + segment[l] = work[k]; + segments.add(segment); + if (slopePoints == null) { - if (!inserted && (ref.compareTo(origin[j]) < 0)) - { - pts[i++] = ref; - pts[i] = origin[j++]; - inserted = true; - } - else - pts[i] = origin[j++]; - i++; + slopePoints = new HashSet<Point>(); + slopePoints.add(last); + slopes.put(sl, slopePoints); + } else + { + slopePoints.add(last); } - if (!inserted) - pts[n - 1] = ref; - else - pts[n - 1] = origin[start + n - 2]; - } - - public boolean equals(Object other) - { - if (other == this) return true; - if (other == null) return false; - if (other.getClass() != this.getClass()) return false; - Segment s = (Segment) other; - if ((pts[0].compareTo(s.pts[0]) == 0) - || (pts[pts.length - 1].compareTo(s.pts[s.pts.length - 1]) == 0)) - return true; - return false; - } - - public void draw() - { - pts[0].drawTo(pts[pts.length-1]); - } - - public void print() - { - String out = ""; - for (Point p : pts) - out += p+" -> "; - StdOut.println(out.substring(0, (out.length() - 4))); } } - private static List<Segment> solve(Point[] pts, int N) + private void solve(Point[] origin, int len) { - List<Segment> segments = new ArrayList<Segment>(); - for (int i = 0; i < N - 1; i++) - { - int n = N - i - 1; - Point ref = pts[i]; - Point[] others = new Point[n]; + this.N = len; + this.pts = origin; + work = new Point[N - 1]; + segments = new ArrayList<Point[]>(); + slopes = new HashMap<Double, HashSet<Point>>(); - for (int j = 0, k = i + 1; j < n; j++, k++) - others[j] = pts[k]; + for (int i = 1, n = N - 1; i < N - 3; i++, n--) + { + // reference [i-1] and copy [i;N[ to [0;n[ + ref = pts[i - 1]; + for (int k = 0, j = i; k < n; k++, j++) + work[k] = pts[j]; - Arrays.sort(others, ref.SLOPE_ORDER); + // sort [0;n[ + Arrays.sort(work, 0, n, ref.SLOPE_ORDER); + // search for sequences >2 in [0;n[ int start = -1; double slope = Double.NEGATIVE_INFINITY; for (int j = 0; j < n; j++) { - double sl = ref.slopeTo(others[j]); + double sl = ref.slopeTo(work[j]); if (sl == Double.NEGATIVE_INFINITY) continue; - if (slope != sl) + if (sl != slope) { if ((start != -1) && ((j - start) > 2)) - { - Segment seg = new Segment(ref, others, - start, (j - start + 1)); - if (!segments.contains(seg)) - segments.add(seg); - } + addSegment(slope, start, j); slope = sl; start = j; } } if ((n - start) > 2) - { - Segment seg = new Segment(ref, others, start, (n - start + 1)); - if (!segments.contains(seg)) - segments.add(seg); - } + addSegment(slope, start, n); + } + for (Point[] seg : segments) + { + seg[0].drawTo(seg[seg.length-1]); + String out = ""; + for (Point p : seg) + out += p+" -> "; + StdOut.println(out.substring(0, (out.length() - 4))); } - return segments; } public static void main(String[] args) { + // Stopwatch w = new Stopwatch(); + In in = new In(args[0]); int n = in.readInt(); @@ -124,13 +112,7 @@ public class Fast } Arrays.sort(pts); - // Stopwatch w = new Stopwatch(); - - for (Segment sol : solve(pts, n)) - { - sol.draw(); - sol.print(); - } + new Fast().solve(pts, n); // StdOut.printf("Time: %f\n\n", w.elapsedTime()); StdDraw.show(0); diff --git a/Algorithms/Part-I/3-Collinear/Point.java b/Algorithms/Part-I/3-Collinear/Point.java index bd5bbe7..1dddb53 100644 --- a/Algorithms/Part-I/3-Collinear/Point.java +++ b/Algorithms/Part-I/3-Collinear/Point.java @@ -67,6 +67,7 @@ public class Point implements Comparable<Point> { // is this point lexicographically smaller than that one? // comparing y-coordinates and breaking ties by x-coordinates public int compareTo(Point that) { + if (this == that) return 0; if (this.y < that.y) return -1; if (this.y > that.y) return 1; if (this.x < that.x) return -1; |