/* vim: set expandtab tabstop=4 shiftwidth=4 : */ import java.util.List; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; public class Fast { private int N; private Point ref; private Point[] pts; // reused each iteration private Point[] work; private List 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> slopes; private void addSegment(double sl, int start, int end) { // 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)) { 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) { slopePoints = new HashSet(); slopePoints.add(last); slopes.put(sl, slopePoints); } else { slopePoints.add(last); } } } private void solve(Point[] origin, int len) { this.N = len; this.pts = origin; work = new Point[N - 1]; segments = new ArrayList(); slopes = new HashMap>(); 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]; // 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(work[j]); if (sl == Double.NEGATIVE_INFINITY) continue; if (sl != slope) { if ((start != -1) && ((j - start) > 2)) addSegment(slope, start, j); slope = sl; start = j; } } if ((n - start) > 2) 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))); } } public static void main(String[] args) { // Stopwatch w = new Stopwatch(); In in = new In(args[0]); int n = in.readInt(); StdDraw.setXscale(0, 32768); StdDraw.setYscale(0, 32768); StdDraw.show(0); Point[] pts = new Point[n]; for (int i = 0; i < n; i++) { pts[i] = new Point(in.readInt(), in.readInt()); pts[i].draw(); } Arrays.sort(pts); new Fast().solve(pts, n); // StdOut.printf("Time: %f\n\n", w.elapsedTime()); StdDraw.show(0); } }