Erect the Fence LeetCode solution in Java

1
class Solution {
2
  public static class Pair {
3
    int x;
4
    int y;
5

6
    Pair(int x, int y) {
7
      this.x = x;
8
      this.y = y;
9
    }
10
  }
11

12
  public int[][] outerTrees(int[][] trees) {
13
    List<Pair> points = new ArrayList<>();
14
    for (int[] point : trees) {
15
      points.add(new Pair(point[0], point[1]));
16
    }
17

18
    List<Pair> res = new ArrayList<>();
19
    if (points.size() == 1) {
20
      return trees;
21
    }
22
    int n = points.size();
23
    Collections.sort(points, (a, b) -> a.y == b.y ? a.x - b.x : a.y - b.y);
24
    HashSet<ArrayList<Integer>> dup = new HashSet<>();
25
    Stack<Pair> hull = new Stack<>();
26

27
    hull.push(points.get(0));
28
    hull.push(points.get(1));
29

30
    for (int i = 2; i < n; i++) {
31
      Pair top = hull.pop();
32
      while (!hull.isEmpty() && ccw(hull.peek(), top, points.get(i)) < 0) {
33
        top = hull.pop();
34
      }
35
      hull.push(top);
36
      hull.push(points.get(i));
37
    }
38
    for (int i = n - 2; i >= 0; i--) {
39
      Pair top = hull.pop();
40
      while (!hull.isEmpty() && ccw(hull.peek(), top, points.get(i)) < 0) {
41
        top = hull.pop();
42
      }
43
      hull.push(top);
44
      hull.push(points.get(i));
45
    }
46

47
    for (Pair p : hull) {
48
      ArrayList<Integer> tmp = new ArrayList<>();
49
      tmp.add(p.x);
50
      tmp.add(p.y);
51
      if (dup.contains(tmp)) continue;
52
      dup.add(tmp);
53
      res.add(p);
54
    }
55

56
    int[][] ans = new int[res.size()][2];
57
    int i = 0;
58
    for (Pair p : res) {
59
      ans[i][0] = p.x;
60
      ans[i][1] = p.y;
61
      i++;
62
    }
63

64
    return ans;
65
  }
66

67
  public int ccw(Pair a, Pair b, Pair c) {
68
    double cp = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
69
    if (cp < 0) return -1;
70
    else if (cp > 0) return 1;
71
    else return 0;
72
  }
73
}