# 963.Minimum-Area-Rectangle-II

## 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 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.
Answers within 10^-5 of the actual value will be accepted as correct.
```

## 代码

### Approach #1 Iterate Triangles

Time: O(N^3) && Space: O(N)

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`.

```java
import java.awt.Point;
class Solution {
  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;
  }
}
```

### Approach #2 Iterate Centers

Time: O(N^2 log N) && Space: O(N)

```java
import java.awt.Point;
class Solution {
  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) + (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).contansKey(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()) {
        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++) {
            // center is twice actual
            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;
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/matrix/963.minimum-area-rectangle-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.