939. Minimum Area Rectangle

對角線就可以確定一個 rec！！ (不需要4點)

怎麼做呢..?

對角線就可以確定一個 rec！！ (不需要4點)

Ａ(x1, y1)                       C (so in Map(x1), find y2 

D (so in Map(x2), find y1        Ｂ(x2, y2) 

另一個 idea, c_d hash string 存 set, 比較慢

T: O(n^2)
S: O(n)

class Solution {
    public int minAreaRect(int[][] points) {
        Map<Integer, HashSet<Integer>> map = new HashMap<>();
        
        for (int[] point : points) {
            map.putIfAbsent(point[0], new HashSet<>());
            map.get(point[0]).add(point[1]);
        }
        
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < points.length; i++) {
            for (int j = i+1; j < points.length; j++) {
                int x1 = points[i][0];
                int y1 = points[i][1];
                int x2 = points[j][0];
                int y2 = points[j][1];
                
                if (x1 == x2 || y1 == y2) {
                    continue;
                }
                if (map.get(x1).contains(y2) && map.get(x2).contains(y1)) {
                    result = Math.min(result, Math.abs(x1-x2)*Math.abs(y1-y2));
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

/*
two pair points' dist is the same


對角線就可以確定一個 rec！！ (不需要4點)

Ａ(x1, y1)                       C (so in Map(x1), find y2 

D (so in Map(x2), find y1        Ｂ(x2, y2) 


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