/* vim: set expandtab tabstop=4 shiftwidth=4 : */ import java.util.List; import java.util.ArrayList; import java.util.Arrays; public class Fast { static class Segment { private Point[] pts; public Segment(Point ref, Point[] origin, int start, int n) { this.pts = new Point[n]; int i = 0; int j = start; boolean inserted = false; while (i < (n - 1)) { if (!inserted && (ref.compareTo(origin[j]) < 0)) { pts[i++] = ref; pts[i] = origin[j++]; inserted = true; } else pts[i] = origin[j++]; i++; } 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))); } } static List solve(Point[] pts, int N) { List segments = new ArrayList(); for (int i = 0; i < N - 1; i++) { int n = N - i - 1; Point ref = pts[i]; Point[] others = new Point[n]; for (int j = 0, k = i + 1; j < n; j++, k++) others[j] = pts[k]; Arrays.sort(others, ref.SLOPE_ORDER); int start = -1; double slope = Double.NEGATIVE_INFINITY; for (int j = 0; j < n; j++) { double sl = ref.slopeTo(others[j]); if (sl == Double.NEGATIVE_INFINITY) continue; if (slope != sl) { if ((start != -1) && ((j - start) > 2)) { Segment seg = new Segment(ref, others, start, (j - start + 1)); if (!segments.contains(seg)) segments.add(seg); } 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); } } return segments; } public static void main(String[] args) { 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); // Stopwatch w = new Stopwatch(); for (Segment sol : solve(pts, n)) { sol.draw(); sol.print(); } // StdOut.printf("Time: %f\n\n", w.elapsedTime()); StdDraw.show(0); } }