You are given an array of points in the X-Y plane points where points[i] = [xi, yi].

Return the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the X and Y axes. If there is not any such rectangle, return 0.

Answers within 10-5 of the actual answer will be accepted.

&nbsp;
Example 1:

Input: points = [[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: points = [[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: points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.


&nbsp;
Constraints:


	1 &lt;= points.length &lt;= 50
	points[i].length == 2
	0 &lt;= xi, yi &lt;= 4 * 104
	All the given points are unique.


class Solution:
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
        N = len(points)
        
        seen = set()
        for point in points:
            seen.add(tuple(point))

        # length^2
        def length2(a, b):
            return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1])
        
        best = 1e30
        for i in range(N):
            for j in range(N):
                if i == j:
                    continue
                
                lij = length2(points[i], points[j])
                for k in range(N):
                    if i == k or j == k:
                        continue
                    
                    # given i->j line, add to k to find l
                    dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]
                    
                    pl = (points[k][0] + dx, points[k][1] + dy)
                    if pl not in seen:
                        continue
                    
                    lik = length2(points[i], points[k])
                    ljk = length2(points[j], points[k])

                    lil = length2(points[i], pl)
                    ljl = length2(points[j], pl)
                    lkl = length2(points[k], pl)
                    
                    if lij == lkl and lik == ljl and lil == ljk:
                        best = min(best, sqrt(lij * lik * lil) / sqrt(max(lij, lik, lil)))
                    
        if best >= 1e29:
            return 0
        return best
class Solution {
    public double minAreaFreeRect(int[][] points) {
        Map<Pair<Double, Double>, Map<Double, List<int[][]>>> map = new HashMap<>();

        double res = Double.MAX_VALUE;
        for (int i = 0; i < points.length; i++) {
            int[] p1 = points[i];
            for (int j = i+1; j < points.length; j++) {
                int[] p2 = points[j];
                // get mid point
                Pair<Double, Double> pm = new Pair((p1[0]+p2[0])/2d, (p1[1]+p2[1])/2d);
                if (!map.containsKey(pm))
                    map.put(pm, new HashMap<>());
                // get diagonal length
                double dist2 = dist2(p1, p2);
                if (!map.get(pm).containsKey(dist2))
                    map.get(pm).put(dist2, new ArrayList<>());

                // calculate area for each pair of p3/p4 and check min
                // Worst case is each pair has same mid point with same length
                // At worst case, below operation costs O(N)
                for (int[][] ps : map.get(pm).get(dist2)) {
                    double d1 = dist2(p1, ps[0]);
                    double d2 = dist2(p1, ps[1]);
                    res = Math.min(res, Math.sqrt(d1 * d2));
                }
                map.get(pm).get(dist2).add(new int[][]{p1, p2});
            }
        }

        return res == Double.MAX_VALUE ? 0 : res;
    }

    private double dist2(int[] p1, int[] p2) {
        return (p2[0]-p1[0])*(p2[0]-p1[0]) + (p2[1]-p1[1])*(p2[1]-p1[1]);
    }
}
#define x1 points[i][0]
#define y1 points[i][1]
#define x2 points[j][0]
#define y2 points[j][1]
#define x3 points[k][0]
#define y3 points[k][1]

class Solution {
public:
  double minAreaFreeRect(vector<vector<int>>& points) {
    int ans = INT_MAX;
    sort(points.begin(),points.end());
    set<pair<int,int>>st;
    for(auto &p: points) st.insert({p[0], p[1]});
    
    for(int i = 0; i != points.size() && ans != 1; i++)
      for(int j = i+1; j != points.size() && ans != 1; j++)
        for(int k = j+1; k != points.size() && ans != 1; k++)
          if( (x1-x2)*(x2-x3)+(y1-y2)*(y2-y3) == 0 && st.count({x1+x3-x2, y1+y3-y2}))
          ans = min(ans, abs( (y1-y2)*(x3-x2) - (x1-x2)*(y3-y2)));
         
    return ans == INT_MAX ? 0.0 : double(ans);
  }
};
/**
 * @param {number[][]} points
 * @return {number}
 */
var minAreaFreeRect = function(points) {
    let len = points.length;
    
    if (len < 4) return 0;
    
    // Helper function to calculate distance
    // between two points, optionally return 
    // without sqrt if want to use as key
    const getDistance = (a, b, isKey = false) => {
        let [xa, ya] = a;
        let [xb, yb] = b;
        
        const distance = (xa - xb) * (xa - xb) + (ya - yb) * (ya - yb);
        return isKey ? distance : Math.sqrt(distance);
    }
    
    let map = new Map();
    
    // let's loop over all points and find all possible
    // diagonals and calc - dis with midpoints and 
    // save as key with co-ordinates as values
    for (let i = 0; i < len; i += 1) {
        for (let j = i + 1; j < len; j += 1) {
            let disKey = getDistance(points[i], points[j], true);
            let [xa, ya] = points[i];
            let [xb, yb] = points[j];
            
            let x = (xa + xb) / 2;
            let y = (ya + yb) / 2;
            
            let key = `${disKey}-${x}-${y}`;
            
            let list = [];
            
            if (!map.has(key)) {
                map.set(key, list)
            } else list = map.get(key);
            
            list.push([i, j]);
            
            map.set(key, list);
        }
    }
    
    // console.log(map);
    let res = Number.MAX_VALUE;
    
    // loop over map of keys above and
    // only iterate through the list where at least 
    // 2 set of co-ordinates have been found above
    map.forEach((list, key) => {
        if (list.length > 1) {
            for (let i = 0; i < list.length; i += 1) {
                for (let j = i + 1; j < list.length; j += 1) {
                    let p1 = list[i][0];
                    let p2 = list[j][0];
                    let p3 = list[j][1];
                    
                    let l = getDistance(points[p1], points[p2]);
                    let b = getDistance(points[p1], points[p3]);
                    res = Math.min(res, l * b);
                }
            }
        }
    })
    
    return res === Number.MAX_VALUE ? 0 : res;
    
};
Minimum Area Rectangle II