963. Minimum Area Rectangle II (Medium)
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.
Solutions
class Solution {
public double minAreaFreeRect(int[][] points) {
int size = points.length;
Point[] oPoints = new Point[size];
Set<Point> pointSet = new HashSet();
for (int i = 0; i < size; ++i) {
oPoints[i] = new Point(points[i][0], points[i][1]);
pointSet.add(oPoints[i]);
}
double ans = Double.MAX_VALUE;
// it's a brute-force solution as well. the time complexity is O(n^3)
for (int i = 0; i < size; ++i) {
Point p1 = oPoints[i];
for (int j = 0; j < size; ++j) {
if (j == i) {
continue;
}
Point p2 = oPoints[j];
// no need to verify whether the link line of these points are parallel to x or y axis,
// since the problem has already stated that sides not necessarily parallel to the x and y axes.
// start from j + 1, otherwise will bring about redundant computation overhead
for (int k = j + 1; k < size; ++k) {
if (k == i) {
continue;
}
Point p3 = oPoints[k];
// assume p1 is right angle of triangle composed of p1,p2,p3, then vector p1p2 must be
// perpendicular p1p3, which means dot production of p1p2 and p1p3 is 0
int dot = ((p2.x - p1.x) * (p3.x - p1.x) + (p2.y - p1.y) * (p3.y - p1.y));
if (dot != 0) {
continue;
}
// we can use formula p0p4=p0p1 + p1p2 + p2p4 to derive the fourth point, where p0 is the
// original point, the trick here is p2p4 can be substituted by p1p3 since it's a rectangle
// for which the opposite edges are required to be parallel.
Point p4 = new Point(p2.x + p3.x - p1.x, p2.y + p3.y - p1.y);
if (!pointSet.contains(p4)) {
continue;
}
double area = p1.distance(p2) * p1.distance(p3);
if (area < ans) {
ans = area;
}
}
}
}
return ans < Double.MAX_VALUE ? ans : 0;
}
class Point {
// when you implement your own Point class, you have to overwrite the equals and hashCode function, or
// points of same coordinate value will not match
public int x = -1;
public int y = -1;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object p) {
if (!(p instanceof Point)) {
return false;
}
Point np = (Point)p;
if (np.x != x || np.y != y) {
return false;
}
return true;
}
@Override
public int hashCode() {
return (x + "#" + y).hashCode();
}
public double distance(Point p) {
return Math.sqrt(Math.pow(x - p.x, 2) + Math.pow(y - p.y, 2));
}
}
}