963. Minimum Area Rectangle II

T: O(n^3)

S: O(n)

class Solution {
    public double minAreaFreeRect(int[][] points) {
        int n = points.length;
        double area = Double.MAX_VALUE;
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] p : points) {
            map.computeIfAbsent(p[0], k -> new HashSet<>()).add(p[1]);
        }
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {
                    int dx1 = points[k][0] - points[i][0];
                    int dy1 = points[k][1] - points[i][1];
                    int dx2 = points[j][0] - points[i][0];
                    int dy2 = points[j][1] - points[i][1];

                    if (dy1*dy2 + dx1*dx2 == 0) {
                        int xl = points[j][0] + dx1;
                        int yl = points[j][1] + dy1;
                        if (map.containsKey(xl) && map.get(xl).contains(yl)) {
                            area = Math.min(area, Math.sqrt(dx1*dx1 + dy1*dy1) * Math.sqrt(dx2*dx2 + dy2*dy2));
                        }
                    }
                }
            }
        }
        return area == Double.MAX_VALUE ? 0 : area;
    }
}

/***
T: O(n^3)
S: O(n)

area = width*height

1. find 3 points fit to "dy1*dy2 + dx1*dx2 = 0;":

                    int dx1 = points[k][0] - points[i][0];
                    int dy1 = points[k][1] - points[i][1];
                    int dx2 = points[j][0] - points[i][0];
                    int dy2 = points[j][1] - points[i][1];
a. (yk - yi)*(yj - yi) + (xj - xi)*(xk - xi) = 0
dy1*dy2 + dx1*dx2 = 0; //  right angles(3 點 -> 兩個邊如果是直角) vector product = 0
  i
j.  k

b. then if we can find 4th point in hashmap

how to find 4th point => 
2 points in x, y -> diagnal intersect is the same 每兩個點的對角線交叉的點 是一樣的
so
   i
j.   k
   l

so we can say... xj xk 的中點, 和 xi xl (4th point) 的中點 是相等的
(xj + xk)/2 = (xi + xl)/2
so the 4th point is:
xl = xj + xk - xi = xj + dx1
yl = yj + dy1 -> and then check is it in map

c.
if we can find the 4th point, cal area
   i
j.   k
   l

a^2 + b^2 = c^2

(xk - xi)^2 + (yk - yi)^2 
=> 
width = sqrt(dx1^2 + dy1^2)
height = sqrt(dx2^2 + dy2^2) 

so area = sqrt(dx1^2 + dy1^2) * sqrt(dx2^2 + dy2^2) 
 */