---
tags: leetcode
---

# [963. Minimum Area Rectangle II](https://leetcode.com/problems/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
<!--
# Test Cases

[[1,2],[2,1],[1,0],[0,1]]

[[0,1],[2,1],[1,1],[1,0],[2,0]]

[[0,3],[1,2],[3,1],[1,3],[2,1]]

* Runtime Error:

[[20214,34113],[5172,14529],[2099,3149],[12650,10018],[13932,15636],[20951,20718],[10343,1948],[12150,11804],[4391,9635],[5151,2363],[14243,2258],[17383,1283],[13751,17958],[5182,130],[8670,9644],[12570,13665],[23573,13878],[11034,24423],[14138,1453],[4694,18],[9492,10425],[20623,6323],[4800,1706],[2450,3806],[4104,4827],[10448,2753],[23232,12867],[20180,12598],[17087,13221],[20084,12850],[14931,12528],[12746,9766],[7631,14675],[10776,6251],[16088,16329],[8250,17769],[32412,22557],[14256,8411],[3616,4715],[16373,11118]]

-->