<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 any rectangle formed from these points, with sides <strong>not necessarily parallel</strong> to the X and Y axes</em>. If there is not any such rectangle, return <code>0</code>.</p>

<p>Answers within <code>10<sup>-5</sup></code> of the actual answer will be accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/21/1a.png" style="width: 398px; height: 400px;" />
<pre>
<strong>Input:</strong> points = [[1,2],[2,1],[1,0],[0,1]]
<strong>Output:</strong> 2.00000
<strong>Explanation:</strong> The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/22/2.png" style="width: 400px; height: 251px;" />
<pre>
<strong>Input:</strong> points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
<strong>Output:</strong> 1.00000
<strong>Explanation:</strong> The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/22/3.png" style="width: 383px; height: 400px;" />
<pre>
<strong>Input:</strong> points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no possible rectangle to form from these points.
</pre>

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

<ul>
	<li><code>1 &lt;= points.length &lt;= 50</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>

/*
1. Two diagonals of a rectangle bisect each other, and are of equal length.
2. The map's key is String including diagonal length and coordinate of the 
diagonal center and map's value is the index of two points forming the diagonal.

*/

class Solution {
public:
    long long distance(vector<int>& p1, vector<int>& p2)
    {
        long long area = (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1]);
        return area;
    }
    
    double minAreaFreeRect(vector<vector<int>>& points) {
        int size = points.size();
        unordered_map<string, vector<vector<int>>> diagnolMap;
        
        for(int i=0; i<size; i++)
        {
            for(int j=i+1; j<size; j++)
            {
                double dist = distance(points[i], points[j]);
                double centerx = (points[i][0]+ points[j][0])/2.0;
                double centery = (points[i][1]+ points[j][1])/2.0;
                string key = to_string(dist)+ "+" + to_string(centerx) + "+" + to_string(centery);
                diagnolMap[key].push_back({i,j});
            }
        }
        
        double minArea = 1e15;
        for(auto it=diagnolMap.begin(); it!=diagnolMap.end(); ++it)
        {
            if(it->second.size() < 2)
            {
                continue;
            }
            
            vector<vector<int>> vec = it->second;
            // there could be multiple rectangles inside
            //in all the points that we have with the same diagnol
            // we want to try all combinations hence using 2 loops
            for(int i=0; i<vec.size(); i++)
            {
                for(int j=i+1; j<vec.size(); j++)
                {
                    //p1, p2 and p3 are the three vertices of a rectangle
                    //p1 is index of a point from one diagnol and 
                    // p2 and p3 are indexes of two points forming same diagnol
                    int p1=vec[i][0], p2=vec[j][0], p3=vec[j][1];
                    long long dist1 = distance(points[p1], points[p2]);
                    long long dist2 = distance(points[p1], points[p3]);
                    double area = (double)dist1*dist2;
                    minArea = min(minArea, sqrt(area));
                }
            }
        }
        return minArea == 1e15? 0.0 : minArea;
    }
};
43744