Formatted question description: https://leetcode.ca/all/963.html

# 963. Minimum Area Rectangle II

Medium

## Description

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

## Solution

For each group of three points, if the three points form a right triangle, then find the right angle and try to find another point such that the four points can form a rectangle, and calculate the area. If a rectangle is found, update the minimum area. If no rectangle is found, return 0.

class Solution {
public double minAreaFreeRect(int[][] points) {
if (points == null || points.length < 4 || points.length != 2)
return 0;
int length = points.length;
double minArea = Double.MAX_VALUE;
int end1 = length - 3, end2 = length - 2, end3 = length - 1;
for (int i = 0; i < end1; i++) {
int[] point1 = points[i];
for (int j = i + 1; j < end2; j++) {
int[] point2 = points[j];
for (int k = j + 1; k < end3; k++) {
int[] point3 = points[k];
if (isRightAngle(point1, point2, point3)) {
for (int m = k + 1; m < length; m++) {
int[] point4 = points[m];
double area = rectangleArea(point1, point2, point3, point4);
if (area > 0)
minArea = Math.min(minArea, area);
}
} else if (isRightAngle(point2, point3, point1)) {
for (int m = k + 1; m < length; m++) {
int[] point4 = points[m];
double area = rectangleArea(point2, point3, point1, point4);
if (area > 0)
minArea = Math.min(minArea, area);
}
} else if (isRightAngle(point3, point1, point2)) {
for (int m = k + 1; m < length; m++) {
int[] point4 = points[m];
double area = rectangleArea(point3, point1, point2, point4);
if (area > 0)
minArea = Math.min(minArea, area);
}
}
}
}
}
return minArea == Double.MAX_VALUE ? 0 : minArea;
}

public double rectangleArea(int[] point1, int[] point2, int[] point3, int[] point4) {
int x = point1 + point3 - point2, y = point1 + point3 - point2;
if (point4 == x && point4 == y) {
double side1 = Math.sqrt((point1 - point2) * (point1 - point2) + (point1 - point2) * (point1 - point2));
double side2 = Math.sqrt((point2 - point3) * (point2 - point3) + (point2 - point3) * (point2 - point3));
return side1 * side2;
} else
return 0;
}

public boolean isRightAngle(int[] point1, int[] point2, int[] point3) {
return (point1 - point2) * (point2 - point3) + (point1 - point2) * (point2 - point3) == 0;

}
}