@Test public void randomTest() { boolean visualize = false; int n = 10; Random r = new Random(); for (int i = 0; i < 1000; i++) { if (i % 100 == 99) n <<= 1; int base = n; int[] p = Shuffler.getRandomArray(2 * n, 0, base); List<Point2D> expectInput = new ArrayList<>(); List<Point2D> testInput = new ArrayList<>(); for (int j = 0; j < p.length; j += 2) { Point2D cur = visualize ? new Point2D(p[j] / base, p[j + 1] / base) : new Point2D(p[j], p[j + 1]); expectInput.add(cur); testInput.add(cur); } GrahamScan expect = new GrahamScan(expectInput.toArray(new Point2D[0])); List<Point2D> exp = new ArrayList<>(); expect.hull().forEach(exp::add); System.out.println("expect:" + exp); List<Point2D> test = ConvexHull.solve(testInput); System.out.println("test:" + test); int idx = 0; for (int expectIdx = 0; expectIdx < exp.size(); expectIdx++) { if (!test.get(idx).equals(exp.get(expectIdx))) { if (visualize) { visualize(expectInput, n, exp, test); } if (checkThePointIsInLinear(test, idx)) { expectIdx--; } else if (checkThePointIsInLinear(exp, expectIdx)) { continue; } else { assertTrue(false); } } idx++; } System.out.println("pass " + i); } }
public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; }
ConvexHull { public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; } }
ConvexHull { public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; }  }
ConvexHull { public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; }  static List<Point2D> solve(List<Point2D> input); static int ccw(Point2D a, Point2D b, Point2D c); }
ConvexHull { public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; }  static List<Point2D> solve(List<Point2D> input); static int ccw(Point2D a, Point2D b, Point2D c);  }