<p>You are given an array of points in the <strong>X-Y</strong> plane <code>points</code> where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>.</p>

<p>Return <em>the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes</em>. If there is not any such rectangle, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/rec1.JPG" style="width: 500px; height: 447px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/rec2.JPG" style="width: 500px; height: 477px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= points.length &lt;= 500</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 4 * 10<sup>4</sup></code></li>
	<li>All the given points are <strong>unique</strong>.</li>
</ul>

class Solution {
public:

    int check(vector<int>&a, vector<int>&b)
    {
        set<int>s;
        map<int,int>m;
        int mn=1e9;

        for(auto x:a)s.insert(x);

        for(auto x:b)if(s.find(x)!=s.end())m[x]++;

        for(auto it=m.begin();it!=m.end();it++)
        {
            auto nxt = it;
            nxt++;
            if(nxt == m.end())break;

            mn = min(mn, nxt->first - it->first);
        }
        return mn;
    }

    int solve(vector<vector<int>>&points, int f, int s)
    {
        map<int,vector<int>>m;
        for(auto p:points)m[p[f]].push_back(p[s]);

        long long mnx, mny, ans;
        mnx = mny = ans = 1e9;

        // for(auto it=m.begin();it!=m.end();it++)
        // {
        //     auto nxt = it;
        //     nxt++;
        //     if(nxt == m.end())break;

        //     mn = min(mn, nxt->first - it->first);
        // }

        // for(auto it=m.begin();it!=m.end();it++)
        // {
        //     auto nxt = it;
        //     nxt++;
        //     if(nxt == m.end())break;

        //    if(nxt->first - it->first == mn)
        //    {
        //         ans = min(ans, check(it->second, nxt->second));
        //    }
        // }

        for(auto it=m.begin();it!=m.end();it++)
        {
            auto nxt = it;nxt++;
            while(nxt!=m.end())
            {
                mny = check(it->second, nxt->second);
                mnx = nxt->first - it->first;
                ans = min(ans, mnx*mny);
                nxt++;
            }
        }

        // cout<<mn<<" "<<ans<<" ; ";
        return ans;
    }

    int minAreaRect(vector<vector<int>>& points) {
        int valx, valy, ans;
        // first x then y
        valx = solve(points, 0, 1);

        // first y then x
        valy = solve(points, 1, 0);

        ans = max(valx, valy);
        if(ans == 1e9)ans = 0;
        
        return ans;
    }
};
381446