https://leetcode.com/problems/minimum-area-rectangle-ii/

minimum-area-rectangle-ii-v1.java

class Solution {
    // vector solution
    public double minAreaFreeRect(int[][] points) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] p : points) {
            if (!map.containsKey(p[0])){
                map.put(p[0], new HashSet<>());
            }
            map.get(p[0]).add(p[1]);
        }
        
        int len = points.length;
        double result = Double.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                // vector point[j] - vector point[i]:  i -> j,  (px1, py1)
                int px1 = points[j][0] - points[i][0];
                int py1 = points[j][1] - points[i][1];
                
                for (int k = j + 1; k < len; k++) {
                    // vector point[k] - vector point[i]:  i -> j,  (px2, py2)
                    int px2 = points[k][0] - points[i][0];
                    int py2 = points[k][1] - points[i][1];                
                    
                    // vector_ij * vector_ik = 0, perpendicular (px1, py1) * (px2, py2) = 0
                    if (px1 * px2 + py1 * py2 != 0) {
                        continue;
                    }
                    // the ideal fourth point vector_ij + point[k]
                    int x = points[k][0] + px1;
                    int y = points[k][1] + py1;
                    if (map.containsKey(x) && map.get(x).contains(y)) {
                        result = Math.min(result, Math.sqrt(px1 * px1 + py1 * py1) * Math.sqrt(px2 * px2 + py2 * py2));
                    }
                }
            }
        }
        
        return result == Double.MAX_VALUE ? 0 : result;
    }
}

minimum-area-rectangle-ii-v2.java

class Solution {
    public double minAreaFreeRect(int[][] points) {
        Map<String, List<int[]>> map = new HashMap<>();
        int len = points.length;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                double dist = computeDist(points[i], points[j]);   
                double[] center = computeCenter(points[i], points[j]);
                String key = center[0] + "," + center[1] + "," + dist;
                if (!map.containsKey(key)) {
                    map.put(key, new ArrayList<>());
                }
                map.get(key).add(new int[]{i, j});
            }
        }
        
        double result = Double.MAX_VALUE;
        for (Map.Entry<String, List<int[]>> entry : map.entrySet()) {
            List<int[]> list = entry.getValue();
            if (list.size() <= 1) {
                continue;
            }
            for (int k = 0; k < list.size(); k++) {
                for(int l = k + 1; l < list.size(); l++) {
                    double res = computeArea(list.get(k)[0], list.get(k)[1], list.get(l)[0], points);
                    result = Math.min(res, result);
                }
            }
        }
        return result == Double.MAX_VALUE ? 0 : result;
    }
    
    
    public double computeDist(int[] p1, int[] p2) {
        return Math.sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]));
    }
    
    public double[] computeCenter(int[] p1, int[] p2) {
        double x = (p1[0] + p2[0]) / 2.0;
        double y = (p1[1] + p2[1]) / 2.0;
        return new double[]{x, y};
    }
    
    public double computeArea(int i, int j, int k, int[][] points) {
        double len1 = computeDist(points[i], points[k]);
        double len2 = computeDist(points[j], points[k]);
        return len1 * len2;
    }
    
    
}