/* vim: set expandtab tabstop=4 shiftwidth=4 : */ import java.util.List; import java.util.ArrayList; import java.util.Arrays; public class Fast { public static void main(String[] args) { class Solution implements Comparable { private Point[] pts; private int n = 0; public Solution(int n) { pts = new Point[n]; } public void add(Point p) { pts[n++] = p; } public void sort() { Insertion.sort(pts); } public void draw() { pts[0].drawTo(pts[n - 1]); } public void print() { String out = ""; for (int i = 0; i < n; i++) out += pts[i]+" -> "; System.out.println(out.substring(0, (out.length() - 4))); } public boolean equals(Object o) { if (o == this) return true; if (o == null) return false; if (o.getClass() != this.getClass()) return false; Solution other = (Solution) o; if (n != other.n) return false; for (int i = 0; i < n; i++) if (pts[i] != other.pts[i]) return false; return true; } public int compareTo(Solution that) { for (int i = 0; i < n; i++) { int r = pts[0].compareTo(that.pts[0]); if (r != 0) return r; } return 0; } } In in = new In(args[0]); int n = in.readInt(); StdDraw.setXscale(0, 32768); StdDraw.setYscale(0, 32768); Point[] pts = new Point[n]; for (int i = 0; i < n; i++) { pts[i] = new Point(in.readInt(), in.readInt()); } List res = new ArrayList(); Point[] others = new Point[n]; for (int i = 0; i < n; i++) { Point ref = pts[i]; ref.draw(); for (int j = 0; j < n; j++) others[j] = pts[j]; Arrays.sort(others, ref.SLOPE_ORDER); int start = 0; double slope = Double.NEGATIVE_INFINITY; for (int j = 1; j < n; j++) { double sl = ref.slopeTo(others[j]); if (sl == Double.NEGATIVE_INFINITY) continue; if (slope != sl) { if ((start != 0) && ((j - start) > 2)) { Solution sol = new Solution(j - start + 1); sol.add(ref); for (int k = start; k < j; k++) sol.add(others[k]); sol.sort(); if (!res.contains(sol)) res.add(sol); } slope = sl; start = j; } } if ((n - start) > 2) { Solution sol = new Solution(n - start + 1); sol.add(ref); for (int k = start; k < n; k++) sol.add(others[k]); sol.sort(); if (!res.contains(sol)) res.add(sol); } } Solution[] sorted = new Solution[res.size()]; res.toArray(sorted); Insertion.sort(sorted); for (Solution sol : sorted) { sol.draw(); sol.print(); } StdDraw.show(0); } }