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. 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.

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

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""