Minimum Area Rectangle II LeetCode solution in Java

1
class Solution {
2
  public double minAreaFreeRect(int[][] points) {
3
    Map<Pair<Double, Double>, Map<Double, List<int[][]>>> map = new HashMap<>();
4

5
    double res = Double.MAX_VALUE;
6
    for (int i = 0; i < points.length; i++) {
7
      int[] p1 = points[i];
8
      for (int j = i + 1; j < points.length; j++) {
9
        int[] p2 = points[j];
10
        // get mid point
11
        Pair<Double, Double> pm = new Pair((p1[0] + p2[0]) / 2d, (p1[1] + p2[1]) / 2d);
12
        if (!map.containsKey(pm)) map.put(pm, new HashMap<>());
13
        // get diagonal length
14
        double dist2 = dist2(p1, p2);
15
        if (!map.get(pm).containsKey(dist2)) map.get(pm).put(dist2, new ArrayList<>());
16

17
        // calculate area for each pair of p3/p4 and check min
18
        // Worst case is each pair has same mid point with same length
19
        // At worst case, below operation costs O(N)
20
        for (int[][] ps : map.get(pm).get(dist2)) {
21
          double d1 = dist2(p1, ps[0]);
22
          double d2 = dist2(p1, ps[1]);
23
          res = Math.min(res, Math.sqrt(d1 * d2));
24
        }
25
        map.get(pm).get(dist2).add(new int[][] {p1, p2});
26
      }
27
    }
28

29
    return res == Double.MAX_VALUE ? 0 : res;
30
  }
31

32
  private double dist2(int[] p1, int[] p2) {
33
    return (p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]);
34
  }
35
}