LeetCode 963 - Minimum Area Rectangle II

Related:
LeetCode 223 - Rectangle Area
LeetCode 850 - Rectangle Area II
LeetCode 939 - Minimum Area Rectangle
LeetCode 963 - Minimum Area Rectangle II
https://leetcode.com/problems/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

https://blog.csdn.net/lwgkzl/article/details/85221883

长方形判定定理：对角线相等，且互相平分的四边形是矩形。

首先平方枚举两个点所构成的所有线段。

对于这些线段把它们当做长方形的一条对角线，确定了这条对角线之后。

枚举第三个点，首先判断第三个点到对角线中点的距离是不是满足对角线长度的一半，（比较距离）

然后判断，与这三个点构成矩形的第四个点是不是存在：讲解一

如果以上两个判断都成立，那么算该长方形的面积（四个点都有了，算出长宽之积就ok）

然后用一个全局变量存满足条件的矩形的最小值就好。

讲解一：

如果判断第四个点存不存在呢？假设p1,p2,p3是已知的三个点。p1,p2构成对角线，对角线的中点是(a,b)

那么第四个点的坐标为：p3.x + (p3.x - a),p3.y + (p3.y - b).其中p3.x-a是p3到中点X轴方向的L1距离，仔细体会一下~

然后用一个map存一下所有的点就可以判断这个点在不在集合内了。



X. https://zhanghuimeng.github.io/post/leetcode-963-minimum-area-rectangle-ii/
枚举圆心和半径

    double minAreaFreeRect(vector<vector<int>>& points) {
        map<pair<Point, int>, vector<int>> mmap;
        vector<Point> p;
        int N = points.size();
        for (int i = 0; i < N; i++)
            p.emplace_back(points[i][0], points[i][1]);
        sort(p.begin(), p.end());
        for (int i = 0; i < N; i++)
            for (int j = i + 1; j < N; j++) {
                Vector v = p[j] - p[i];
                mmap[make_pair((p[i] + p[j]) / 2, v.length2())].push_back(i);
            }
        double ans = -1;
        for (const auto& pa: mmap) {
            Point center = pa.first.first;
            for (int i = 0; i < pa.second.size(); i++) {
                // cout << pa.second[i] << ' ';
                for (int j = i + 1; j < pa.second.size(); j++) {
                    int i1 = pa.second[i], j1 = pa.second[j]; 
                    double area = 2 * abs(cross(p[i1] - center, p[j1] - center));
                    ans = ans < 0 ? area : min(ans, area);
                }
            }
        }
        return max(ans, 0.0);
    }

https://jinx19.github.io/2018/12/24/LeetCode-Solution-2018-12-24-LeetCode-Solution-963-Minimum-Area-Rectangle-II/

考虑矩形ABCD的对角点AC和BD,它们有相同的中心O，即AC的中点和AB的中点;并且它们都具有相同的半径dist（O，A）== dist（O，B）== dist（O，C）== dist（O，D）。

在该结果的推动下，让我们将每对点PQ分类为它们的中心C = PQ的中点，并且半径r = dist（P，C）。我们的策略是对具有相同分类的成对点进行暴力破解。

对于每对点，按中心和半径对它们进行分类。我们只需要记录其中一个点P，因为另一个点是P’= 2 * center-P（使用矢量符号）。

对于每个中心和半径，查看每个可能的矩形（两对点P，P’，Q，Q’）。该矩形dist（P，Q）* dist（P，Q’）的面积是候选答案。

https://leetcode.com/articles/minimum-area-rectangle-ii/
Approach 2: Iterate Centers

• Time Complexity: $O(N^2 \log N)$, where $N$ is the length of points. It can be shown that the number of pairs of points with the same classification is bounded by $\log N$ - see this link for more.
• Space Complexity: $O(N)$.

Consider opposite points AC and BD of a rectangle ABCD. They both have the same center O, which is the midpoint of AC and the midpoint of AB; and they both have the same radius dist(O, A) == dist(O, B) == dist(O, C) == dist(O, D). Notice that a necessary and sufficient condition to form a rectangle with two opposite pairs of points is that the points must have the same center and radius.

Motivated by that result, let's classify each pair of points PQ by their center C = the midpoint of PQ, and the radius r = dist(P, C). Our strategy is to brute force on pairs of points with the same classification.

Algorithm

For each pair of points, classify them by center and radius. We only need to record one of the points P, since the other point is P' = 2 * center - P (using vector notation).

For each center and radius, look at every possible rectangle (two pairs of points P, P', Q, Q'). The area of this rectangle dist(P, Q) * dist(P, Q') is a candidate answer.

  public double minAreaFreeRect(int[][] points) {

    int N = points.length;

    Point[] A = new Point[N];

    for (int i = 0; i < N; ++i)

      A[i] = new Point(points[i][0], points[i][1]);

    Map<Integer, Map<Point, List<Point>>> seen = new HashMap();

    for (int i = 0; i < N; ++i)

      for (int j = i + 1; j < N; ++j) {

        // center is twice actual to keep integer precision

        Point center = new Point(A[i].x + A[j].x, A[i].y + A[j].y);

        int r2 = (A[i].x - A[j].x) * (A[i].x - A[j].x);

        r2 += (A[i].y - A[j].y) * (A[i].y - A[j].y);

        if (!seen.containsKey(r2))

          seen.put(r2, new HashMap<Point, List<Point>>());

        if (!seen.get(r2).containsKey(center))

          seen.get(r2).put(center, new ArrayList<Point>());

        seen.get(r2).get(center).add(A[i]);

      }

    double ans = Double.MAX_VALUE;

    for (Map<Point, List<Point>> info : seen.values()) {

      for (Point center : info.keySet()) { // center is twice actual

        List<Point> candidates = info.get(center);

        int clen = candidates.size();

        for (int i = 0; i < clen; ++i)

          for (int j = i + 1; j < clen; ++j) {

            Point P = candidates.get(i);

            Point Q = candidates.get(j);

            Point Q2 = new Point(center);

            Q2.translate(-Q.x, -Q.y);

            double area = P.distance(Q) * P.distance(Q2);

            if (area < ans)

              ans = area;

          }

      }

    }

    return ans < Double.MAX_VALUE ? ans : 0;

  }

For each triangle, let's try to find the 4th point and whether it is a rectangle.

Say the first 3 points are p1, p2, p3, and that p2 and p3 are opposite corners of the final rectangle. The 4th point must be p4 = p2 + p3 - p1 (using vector notation) because p1, p2, p4, p3 must form a parallelogram, and p1 + (p2 - p1) + (p3 - p1) = p4.

If this point exists in our collection (we can use a HashSet to check), then we should check that the angles of this parallelogram are 90 degrees. The easiest way is to check the dot product of the two vectors (p2 - p1) and (p3 - p1). (Another way is we could normalize the vectors to length 1, and check that one equals the other rotated by 90 degrees.)

• Time Complexity: $O(N^3)$, where $N$ is the length of points.

  public double minAreaFreeRect(int[][] points) {

    int N = points.length;

    Point[] A = new Point[N];

    Set<Point> pointSet = new HashSet();

    for (int i = 0; i < N; ++i) {

      A[i] = new Point(points[i][0], points[i][1]);

      pointSet.add(A[i]);

    }

    double ans = Double.MAX_VALUE;

    for (int i = 0; i < N; ++i) {

      Point p1 = A[i];

      for (int j = 0; j < N; ++j)

        if (j != i) {

          Point p2 = A[j];

          for (int k = j + 1; k < N; ++k)

            if (k != i) {

              Point p3 = A[k];

              Point p4 = new Point(p2.x + p3.x - p1.x, p2.y + p3.y - p1.y);

              if (pointSet.contains(p4)) {

                int dot = ((p2.x - p1.x) * (p3.x - p1.x) + (p2.y - p1.y) * (p3.y - p1.y));

                if (dot == 0) {

                  double area = p1.distance(p2) * p1.distance(p3);

                  if (area < ans)

                    ans = area;

                }

              }

            }

        }

    }

    return ans < Double.MAX_VALUE ? ans : 0;

  }

X. O(N^3)

如果p4在集合内，则检查对角线的角度是否为90度，即是否为正方形。
最简单的方法是检查角度， 利用直角三角形的特性：两直角边边长的平方和等于斜边长的平方
最简单的方法是检查两个向量（p2 - p1）和（p3 - p1）的点积
两向量内积为0说明向量垂直

高数向量积的知识点 = =
https://www.cnblogs.com/xiexinxinlove/p/3708147.html
https://www.wikiwand.com/zh/%E5%A4%8D%E6%95%B0_(%E6%95%B0%E5%AD%A6))
http://www.voidcn.com/article/p-mlgshcsk-op.html

http://www.programmersought.com/article/5527381097/

    public double minAreaFreeRect(int[][] points) {
        Set<String> set = new HashSet<>();
        double result = Double.MAX_VALUE;
        // construct point set
        for(int[] p : points){
            set.add(p[0] + " " + p[1]);
        }
        / / Through the third point to find the fourth point
        for(int[] p1 : points){
            for(int[] p2 : points){
                if(p1[0] == p2[0] && p1[1] == p2[1]){
                    continue;
                }
                for(int[] p3 : points){
                    / / Pythagorean
                    if(dist(p1, p3) + dist(p2, p3) != dist(p1, p2)){
                        continue;
                    }
                    / / The coordinates of the fourth point
                    int x = p1[0] + p2[0] - p3[0];
                    int y = p1[1] + p2[1] - p3[1];
                    / / Whether the fourth point exists in the point set
                    if(!set.contains(x + " " + y)){
                        continue;
                    }
                    double area = Math.sqrt(dist(p1, p3)) * Math.sqrt(dist(p2, p3));
                    if(area == 0){
                        continue;
                    }
                    result = Math.min(result, area);
                }
            }
        }
        return result == Double.MAX_VALUE ? 0 : result;
    }
    public double dist(int[] x1, int[] x2){
        return (x1[0] - x2[0]) * (x1[0] - x2[0]) + (x1[1] - x2[1]) * (x1[1] - x2[1]);
    }
}

(枚举) O(n3)O(n3)
将所有点加入哈希表中。
每次枚举三个点 x, y, z，以这三个点尝试构成矩形的一组邻边，共有三种情况。假设 (x, y) 和 (x, z) 构成一组邻边，判定其是否垂直，即点乘为 0。然后，通过向量运算求出另一个点 p，使得 (x, y) 与 (z, p) 是相同的向量。在哈希表中判断 p 是否存在即可。
https://leetcode.com/problems/minimum-area-rectangle-ii/discuss/208377/Python-easy-to-understand-dot-product-O(N3)-AC

• Dot product of two sides in a rectangle should be zero because a . b = |a| |b| cos(90)
• If we can extend p3 by the same margin delta(p2 - p1), we can have the fourth point p4.
  • x4 = x3 + (x2 - x1)
  • y4 = y3 + (y2 - y1)
• If p4 in points, calculate area.

https://leetcode.com/problems/minimum-area-rectangle-ii/discuss/208361/JAVA-O(n2)-using-Map
In the worst case it is still O(N^3): simply consider all diagonal bisect each other and of equal length.

1. Two diagonals of a rectangle bisect each other, and are of equal length.
2. The map's key is String including diagonal length and coordinate of the diagonal center; map's value is the index of two points forming the diagonal

    public double minAreaFreeRect(int[][] points) {
        int len = points.length;
        double res = Double.MAX_VALUE;
        if (len < 4) return 0.0;
        Map<String, List<int[]>> map = new HashMap<>(); // int[] is the index of two points forming the diagonal
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                long dis = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                double centerX = (double)(points[j][0] + points[i][0])/2; // centerX and centerY is the coordinate of the diagonal center
                double centerY = (double)(points[j][1] + points[i][1])/2;
                String key = "" + dis + "+" + centerX + "+" + centerY; // key includes the length of the diagonal and the coordinate of the diagonal center
                if (map.get(key) == null) map.put(key, new ArrayList<int[]>());
                map.get(key).add(new int[]{i,j});
            }
        }
        for (String key : map.keySet()) {
            if (map.get(key).size() > 1) {  
                List<int[]> list = map.get(key);
                for (int i = 0; i < list.size(); i++) { // there could be multiple rectangles inside
                    for (int j = i + 1; j < list.size(); j++) {
                        int p1 = list.get(i)[0]; // p1, p2 and p3 are the three vertices of a rectangle
                        int p2 = list.get(j)[0];
                        int p3 = list.get(j)[1];
                        // len1 and len2 are the length of the sides of a rectangle
                        double len1 = Math.sqrt((points[p1][0] - points[p2][0]) * (points[p1][0] - points[p2][0]) +  (points[p1][1] - points[p2][1]) * (points[p1][1] - points[p2][1])); 
                        double len2 = Math.sqrt((points[p1][0] - points[p3][0]) * (points[p1][0] - points[p3][0]) +  (points[p1][1] - points[p3][1]) * (points[p1][1] - points[p3][1]));
                        double area = len1 * len2; 
                        res = Math.min(res, area);
                    }
                }
            }
        }
        return res == Double.MAX_VALUE ?  0.0 : res;
    }