Minimum Area Rectangle II

Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.

If there isn't any rectangle, return 0.

 

Example 1:

Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Example 4:

Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.

 

Note:

1. 1 <= points.length <= 50
2. 0 <= points[i][0] <= 40000
3. 0 <= points[i][1] <= 40000
4. All points are distinct.
5. Answers within 10^-5 of the actual value will be accepted as correct.

 

题目理解：

给定一系列二维平面中的坐标点，找出这些坐标点所表示的矩形，求出面积最小的矩形的面积

解题思路：

找到由坐标点构成的每一条线段，将斜率相同的线段放到一起，因为只有斜率相同的两条线段才有可能组成矩形。

然后遍历所有的斜率组，对于其中的线段a和线段b，判断他们的长度是否相同，判断相邻的边是否垂直，来确定这两条线段能够组成矩形。在所有合法的矩形中记录最小的面积。

有两个需要注意的问题：

1.没有斜率，也就是和x轴垂直的线段怎么处理？答案是不用处理，因为如果能构成矩形，那么这个矩形的另外两条边时有斜率的，因此这个矩形是能够被找到的。

2.如何判断垂直？使用向量相乘的方式来判断垂直，但是这里需要注意，一定要是两条邻边，如果不注意的话，可能会弄成一条边和一条对角线，避免这个问题的方法，是给构成线段的两个点排序，横坐标小的在前面，大的在后面，这样在计算向量的时候就不会弄混。排序的方法有很多，最简单的一种就是给所有点按照横坐标排序，然后在遍历斜率的时候按前后顺序遍历。

class Solution {
    public double getSlope(int[] a, int[] b){
        return (double)(a[1] - b[1]) / (a[0] - b[0]);
    }

    public double judge(int[] a1, int[] a2, int[] b1, int[] b2){
        long len1 = (long)(a1[0] - a2[0]) * (a1[0] - a2[0]) + (long)(a1[1] - a2[1]) * (a1[1] - a2[1]);
        long len2 = (long)(b1[0] - b2[0]) * (b1[0] - b2[0]) + (long)(b1[1] - b2[1]) * (b1[1] - b2[1]);
        if(len1 != len2)
            return -1;
        int[] vec_a = new int[]{a1[0] - a2[0], a1[1] - a2[1]};
        int[] vec_ab = new int[]{b1[0] - a1[0], b1[1] - a1[1]};
        long len_ab = (long)(a1[0] - b1[0]) * (a1[0] - b1[0]) + (long)(a1[1] - b1[1]) * (a1[1] - b1[1]);
        if(vec_a[0] * vec_ab[0] + vec_a[1] * vec_ab[1] == 0)
            return Math.sqrt(len1) * Math.sqrt(len_ab);
        return -1;
    }

    public double minAreaFreeRect(int[][] points) {
        Map<Double, List<int[]>> map = new HashMap<>();
        List<int[]> vertical = new ArrayList<>();
        int len = points.length;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] != o2[0])
                    return o1[0] - o2[0];
                else
                    return o1[1] - o2[1];
            }
        });
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                //vertical
                if(points[i][0] == points[j][0]){
                    vertical.add(new int[]{i, j});
                }
                else{
                    double slope = getSlope(points[i], points[j]);
                    List<int[]> list = map.getOrDefault(slope, new ArrayList<int[]>());
                    list.add(new int[]{i, j});
                    map.put(slope, list);
                }
            }
        }
        double res = 0;
        for(double key : map.keySet()){
            List<int[]> list = map.get(key);
            //System.out.println(key + ": " + list.toArray());
            int size = list.size();
            for(int i = 0; i < size; i++){
                for(int j = i + 1; j < size; j++){
                    //System.out.println(i + " " + j);
                    int[] a = list.get(i), b = list.get(j);
                    double cur = judge(points[a[0]], points[a[1]], points[b[0]], points[b[1]]);
                    if(cur != -1){
                        if(res == 0 || res > cur)
                            res = cur;
                    }
                }
            }
        }
        return res;
    }
}