963. Minimum Area Rectangle II

---

My Solution

The Key Idea for Solving This Coding Question

C++ Code

#define MAX_X (40001)
#define MAX_Y (40001)

class Solution {
public:
    double minAreaFreeRect(vector<vector<int>> &points) {
        unordered_set<int> hashedPoints;
        for (auto &point : points) {
            hashedPoints.insert(encode(point[0], point[1]));
        }

        double minArea = DBL_MAX;
        bool foundRec = false;
        for (int i = 0; i < points.size(); ++i) {
            for (int j = 0; j < points.size(); ++j) {
                if (i == j) {
                    continue;
                }
                for (int k = 0; k < points.size(); ++k) {
                    if (i == k || j == k) {
                        continue;
                    }
                    int x1 = points[i][0], y1 = points[i][1];
                    int x2 = points[j][0], y2 = points[j][1];
                    int x3 = points[k][0], y3 = points[k][1];
                    unsigned long side1 = getLen(x1, y1, x2, y2);
                    unsigned long side2 = getLen(x2, y2, x3, y3);
                    unsigned long diagonal = getLen(x1, y1, x3, y3);
                    if (side1 + side2 != diagonal) {
                        continue;
                    }

                    int x4 = x3 + x1 - x2, y4 = y3 + y1 - y2;
                    if (hashedPoints.find(encode(x4, y4)) == hashedPoints.end()) {
                        continue;
                    }

                    foundRec = true;
                    minArea = min(minArea, sqrt(side1) * sqrt(side2));
                }
            }
        }

        if (!foundRec) {
            return 0.0;
        }
        return minArea;
    }

private:
    int encode(int x, int y) {
        return x * MAX_Y + y;
    }

    void decode(int code, int &x, int &y) {
        x = code / MAX_Y;
        y = code % MAX_Y;
    }

    unsigned long getLen(int x1, int y1, int x2, int y2) {
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    }
};

Time Complexity

Space Complexity

Miscellane