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.

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)

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;
  }
}