class Solution {
public:
    double maxAreaRect(vector<vector<double>>& p) {
        double n = p.size(), max_area = -1; // store max area
        
        // key -> mid point of 2 (x, y), and their length to mid point((double, double), double)
        // val -> the 2 (x, y)(unordered_set of 2d double vector)
        unordered_map<vector<double>, unordered_set<vector<vector<double>>>> m; 
        m.emplace(vector<double>{}, unordered_set<vector<vector<double>>>{}); // a hash map
        // use unordered data structure because sorted structure might cost more time when sorting for us
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {              
                double mid_x = (p[i][0] + p[j][0]) / 2, mid_y = (p[i][1] + p[j][1]) / 2;
                double mid_dis = sqrt(pow((p[i][0] - mid_x), 2) + pow((p[i][1] - mid_y), 2));
                m[{mid_x, mid_y}].insert({p[i], p[j]});  
            }
        }
        
        for (auto m_it = m.begin(); m_it != m.end(); m_it++) {
            auto ms = m_it->second;
            if (ms.size() < 2) continue;
            else {
                // if 2 pair of different (x, y) have same mid point and length to mid point
                // they must form a rectangle and it's impossible for a point to have same mid point with 2 different point
                for (auto s_it1 = ms.begin(); s_it1 != ms.end(); s_it1++) {
                    auto tmp_v1 = *s_it1; // get first 2 points
                    double x1 = tmp_v1[0][0], y1 = tmp_v1[0][1], x2 = tmp_v1[1][0], y2 = tmp_v1[1][1];
                    // compare with other points
                    auto s_it2 = s_it1; 
                    if (s_it2 != ms.end()) s_it2++;
                    for (; s_it2 != ms.end(); s_it2++) { 
                        // get next 2 points
                        auto tmp_v2 = *s_it2;
                        double x3 = tmp_v2[0][0], y3 = tmp_v2[0][1], x4 = tmp_v2[1][0], y4 = tmp_v2[1][1];
                        double edge1 = sqrt(pow((x1 - x3), 2) + pow((x2 - x3), 2));
                        double edge2 = sqrt(pow((y1 - y3), 2) + pow((y2 - y3), 2));
                        max_area = max(max_area, edge1 * edge2); // store max area
                    }
                }
            }
        }
        
        return max_area;
    }
};