Minimum Area Rectangle II

LeetCode Q 963 - 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.

Solution

• How to identify two edges(a and b) can form a right angle?
  We can use vector theory. Regard two edges as two vectors. The dot product of vector a and b is
  a . b = |a| * |b| * cos(theta)
  Vector a and b can form a right angle means theta = 90. Then we can infer
  a . b = |a| * |b| * cos(theta) = 0.
• How to calculate dot multiplication of two vectors?
  a . b = a1b1 + a2b2 + a3b3 + ...

Code:

public double minAreaFreeRect(int[][] points) {
  Set<String> set = new HashSet<>();
  for (int[] point: points) {
    int x = point[0], y = point[1];
    set.add(x + "," + y);
  }
  
  double minArea = Double.MAX_VALUE;
  for (int i = 0; i < points.length; i++) {
    for (int j = 0; j < points.length; j++) {
      for (int k = j + 1; k < points.length; k++) {
        if (i == j || i == k) continue;
        
        int[] p1 = points[i];
        int[] p2 = points[j];
        int[] p3 = points[k];
        
        if( (p2[0] - p1[0])*(p3[0] - p1[0]) 
          + (p2[1] - p1[1])*(p3[1] - p1[1]) != 0) continue;
        
        // x4 = x3 + (x2 - x1)
        // y4 = y3 + (y2 - y1)
        int x = p2[0] - p1[0] + p3[0];
        int y = p2[1] - p1[1] + p3[1];
        if (!set.contains(x + "," + y)) continue;
        
        double area = square(p1, p2, p3);
        if (area == 0) continue;
        
        minArea = Math.min(minArea, area);
      }
    }
  }
  return minArea == Double.MAX_VALUE ? 0: minArea;
}

private double square(int[] p1, int[] p2, int[] p3) {
  double width = distance(p1,p2);
  double length = distance(p1, p3);
  return Math.sqrt(width * length);
}

// get distance^2, use double to avoid overflow
private double distance(int[] p1, int[] p2) {
  return 1.0D * (p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]);
}