LeetCode [963] Minimum Area Rectangle II

 963. Minimum Area Rectangle II

Medium

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

class Solution { double E = 0.00001; int[][] points; double getD(int i, int j){ return Math.sqrt(Math.pow(points[i][0]-points[j][0], 2) + Math.pow(points[i][1]-points[j][1], 2)); } boolean valid(int i, int j, int u, int v){ double xm = (double)(points[i][0]+points[j][0])/2.0; double ym = (double)(points[i][1]+points[j][1])/2.0; double xm0 = (double)(points[u][0]+points[v][0])/2.0; double ym0 = (double)(points[u][1]+points[v][1])/2.0; if(Math.abs(xm-xm0)>E || Math.abs(ym-ym0)>E) return false; if(Math.abs(getD( i, j)-getD(u, v))>E) return false; return true; } public double minAreaFreeRect(int[][] points) { this.points = points; int n = points.length; double area = 0; for(int i=0; i<n; ++i){ for(int j=i+1; j<n; ++j){ for(int u=0; u<n; ++u){ if(u==i || u==j) continue; for(int v=u+1; v<n; ++v){ if(v==i || v==j) continue; if(valid(i, j, u, v)){ double t = getD(i, u)*getD(i, v); if(area==0) area = t; area = Math.min(area, t); } } } } } return area; } }