Minimum Area Rectangle II_2.cpp

struct Dot
{
    int x, y;
    
    Dot(int i, int j)
    {
        x = i;
        y = j;
    }
    
    bool operator==(const Dot& that)const
    {
        return x == that.x && y == that.y;
    }
};

struct Hasher
{
    size_t operator()(const Dot& point)const
    {
        string str = to_string(point.x) + ":" + to_string(point.y);
        return hash<string>()(str);
    }
};

class Solution {
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
        int len = points.size();
        //user center and radius to track possible candidate points
        //since we won't use double for hash set, we use 2 * center and
        //radius^2 for hashmap key
        unordered_map<Dot, unordered_map<int, vector<Dot>>, Hasher> map;
        for(int i = 0; i < len; ++i)
        {
            for(int j = i + 1; j < len; ++j)
            {
                Dot p0(points[i][0], points[i][1]), p1(points[j][0], points[j][1]);
                Dot center(p0.x + p1.x, p0.y + p1.y);
                int radius = (p0.x - p1.x) * (p0.x - p1.x);
                radius += (p0.y - p1.y) * (p0.y - p1.y);
                map[center][radius].push_back(p0);
            }
        }
        double res = 40005 * 40005;
        for(auto& cmap : map)
        {
            Dot center = cmap.first;
            for(auto& rmap : cmap.second)
            {
                int radius = rmap.first;
                auto dots = rmap.second;
                for(int i = 0; i < dots.size(); ++i)
                {
                    for(int j = i + 1; j < dots.size(); ++j)
                    {
                        Dot p0 = dots[i], p1 = dots[j];
                        Dot p2(center.x - p1.x, center.y - p1.y);
                        double e1 = getLen(p0, p1), e2 = getLen(p0, p2);
                        res = min(res, e1 * e2);
                    }
                }
            }          
        }
        return res < 40005 * 40005? res : 0;
    }
    
private:
    
    double getLen(const Dot& p0, const Dot& p1)
    {
        return sqrt(pow(p1.x - p0.x, 2) + pow(p1.y - p0.y, 2));
    }
};