### Question:
ConvexHull { public static List<Point2D> solve(List<Point2D> input) { return null; }  static List<Point2D> solve(List<Point2D> input); static int ccw(Point2D a, Point2D b, Point2D c);  }### Answer:
@Test public void basicTest() { List<Point2D> expectInput = new ArrayList<>(); expectInput.add(new Point2D(1, 1)); expectInput.add(new Point2D(0, 0)); expectInput.add(new Point2D(2, 2)); List<Point2D> testInput = new ArrayList<>(expectInput); GrahamScan expect = new GrahamScan(expectInput.toArray(new Point2D[0])); List<Point2D> test = ConvexHull.solve(testInput); int i = 0; for (Point2D p : expect.hull()) { assertTrue(test.get(i).equals(p)); i++; } }
@Test public void basicTest2() { List<Point2D> expectInput = new ArrayList<>(); expectInput.add(new Point2D(1, 1)); expectInput.add(new Point2D(4, 1)); expectInput.add(new Point2D(7, 5)); expectInput.add(new Point2D(7, 6)); expectInput.add(new Point2D(0, 8)); expectInput.add(new Point2D(0, 2)); List<Point2D> testInput = new ArrayList<>(expectInput); GrahamScan expect = new GrahamScan(expectInput.toArray(new Point2D[0])); List<Point2D> test = ConvexHull.solve(testInput); int i = 0; for (Point2D p : expect.hull()) { assertTrue(test.get(i).equals(p)); i++; } }
@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); } }