[Geometry] Smallest rectangle in cloud of points

solution-Minimum-Area-Rectangle.md

The problem is to find all rectangular of minimal area spanned on 4 points from the given set. See lc.

The brute force solution is to have a cache of already tackled points and for each current point and for each point in cache we are looking in the cache if necessary 2 other points existed. Beside of fast search, the cache of seen points also allows to avoid considering dublicates.

    struct Hash {
        size_t operator()(const pair<int,int>&x)const{
            return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
        }
    };
    // solution 1 - 416ms, 16MB
    int minAreaRect(vector<vector<int>>& points) {
        unordered_set<pair<int,int>, Hash> seen;
        int res = numeric_limits<int>::max();
        for (const auto& p : points) {
            int x1 = p[0], y1 = p[1];
            for (auto[x2,y2] : seen) 
                if (seen.count({x1, y2}) && seen.count({x2, y1})) {
                    int area = abs(x1 - x2)*abs(y1 - y2);
                    res = min(area, res);
                }
            
            seen.emplace(x1, y1);
        }
        return res == numeric_limits<int>::max() ? 0 : res;
    }

For the second solution, we sort points by x from left to right (achieved by using map) and traverse through x coordinate. For each x, we have a set of ys. For each pair in this set we need to search a matching pair on the left. The condition j < i is just to avoid considering dublicates. So, one more time, if the current pair of ys is y1, y2 we need to find exactly the same pair of ys with different x in the past. Moreover, it is enough to consider the closest in the past pair of y1, y2 because if there exists a pair erlier it gives larger rectangle.

    // Solution 2
    pair<int,int> count(vector<vector<int>>& points) {
        unordered_set<int> xs, ys;
        for (auto& p : points) {
            xs.insert(p[0]);
            ys.insert(p[1]);
        }
        return {xs.size(), ys.size()};
    }
    
    int minAreaRect(vector<vector<int>>& points) {
        // optimization - count distinct x and y
        const auto&[nx, ny] = count(points);
        if (nx == 0 || ny == 0) return 0; // gives -20ms
        
        // this optimization gives total runtime improvement x10
        map<int, vector<int>> x2y;
        if (nx > ny)
            for (auto& p : points)
                x2y[p[0]].emplace_back(p[1]);
        else
            for (auto& p : points)
                x2y[p[1]].emplace_back(p[0]);
        
        unordered_map<pair<int,int>, int, Hash> seenPairsOfY2X;
        int res = numeric_limits<int>::max();
        for (auto&[x, ys] : x2y) {
            sort(ys.begin(), ys.end());
            for (int i = 0; i < ys.size(); ++i)
                for (int j = 0; j < i; ++j) {
                    int y1 = ys[j], y2 = ys[i]; // y2 > y1
                    if (seenPairsOfY2X.count({y1,y2})) {
                        int x1 = seenPairsOfY2X[{y1,y2}];
                        int x2 = x;
                        int area = (y2 - y1) * (x2 - x1);
                        res = min(res, area);
                    }
                    seenPairsOfY2X[{y1,y2}] = x;
                }
        }
        return res == numeric_limits<int>::max() ? 0 : res;   
    }
};