Geometric problems

939. Minimum Area Rectangle

Find two points of the diagonal of the rectangle, then find the rest two points.

if the two points of the diagonal are A(x1, y1), B(x2, y2), then the rest two points will be (x1, y2), (x2, y1)

The following solution complexity is O(n²) if we ignore the complexity of map and set find operations. However, it got TLE.

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        map<int, set<int>> xs, ys;
        for(auto p: points)
        {
            auto x = p[0], y = p[1];
            xs[x].insert(y); ys[y].insert(x);
        }
        const int n = points.size();
        int ret = INT_MAX;
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
            {
                auto x1 = points[i][0], y1 = points[i][1];
                auto x2 = points[j][0], y2 = points[j][1];
                if(x1==x2 || y1==y2)continue;
                //(x1, y2), (x2, y1)
                if(xs[x1].count(y2) && ys[y1].count(x2))ret = min(ret, abs(x1-x2)*abs(y1-y2));
            }
        return ret==INT_MAX?0:ret;
    }
};

change the map and set to unordered_map and unordered_set, still got TLE.

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        unordered_map<int, unordered_set<int>> xs, ys;
        for(auto p: points)
        {
            auto x = p[0], y = p[1];
            xs[x].insert(y); ys[y].insert(x);
        }
        const int n = points.size();
        int ret = INT_MAX;
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
            {
                auto x1 = points[i][0], y1 = points[i][1];
                auto x2 = points[j][0], y2 = points[j][1];
                if(x1==x2 || y1==y2)continue;
                //(x1, y2), (x2, y1)
                if(xs[x1].count(y2) && ys[y1].count(x2))ret = min(ret, abs(x1-x2)*abs(y1-y2));
            }
        return ret==INT_MAX?0:ret;
    }
};

Slightly change the code got AC.

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        unordered_map<int, unordered_set<int>> xs, ys;
        for(auto &p: points)
        {
            xs[p[0]].insert(p[1]); ys[p[1]].insert(p[0]);
        }
        const int n = points.size();
        int ret = INT_MAX;
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
            {
                //auto x1 = points[i][0], y1 = points[i][1];
                //auto x2 = points[j][0], y2 = points[j][1];
                if(points[i][0]==points[j][0] || points[i][1]==points[j][1])continue;
                //(x1, y2), (x2, y1)
                if(xs[points[i][0]].count(points[j][1]) && ys[points[i][1]].count(points[j][0]))ret = min(ret, abs(points[i][0]-points[j][0])*abs(points[i][1]-points[j][1]));
            }
        return ret==INT_MAX?0:ret;
    }
};

A better one

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        int res = INT_MAX;
        unordered_map<int, set<int>> x;
        for (auto p : points) x[p[0]].insert(p[1]);
        for (auto i = x.begin(); i != x.end(); ++i)
            for (auto j = next(i); j != x.end(); ++j)
            {
                if (i->second.size() < 2 || j->second.size() < 2) continue;
                vector<int> y;
                set_intersection(begin(i->second), end(i->second),
                                 begin(j->second), end(j->second), back_inserter(y));
                for (int k = 1; k < y.size(); ++k)
                    res = min(res, abs(j->first - i->first) * (y[k] - y[k - 1]));
            }
        return res == INT_MAX ? 0 : res;
    }
};

About set_intersection and back_inserter

An example of how to use them can be found HERE.