391. 完美矩形

2022-01-15  本文已影响0人  来到了没有知识的荒原

391. 完美矩形

几个约束条件:

  1. 相加面积等于区域面积(区域面积由最左下角的点和最右上角的点张成(可能是不存在的虚拟点,这种请况就是不合法的))
  2. 4个顶点的count都为1
  3. 内部的所有点count不是2就是4
typedef long long ll;
class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rs) {
        vector<int> left(2,INT_MAX),right(2,0);
        for(auto &r:rs){
            left[0]=min(left[0],r[0]);
            left[1]=min(left[1],r[1]);
            right[0]=max(right[0],r[2]);
            right[1]=max(right[1],r[3]);
        }
        ll area=1ll*(right[0]-left[0])*(right[1]-left[1]);
        ll sum=0;
        map<pair<int,int>,int>mp;
        for(auto r:rs){
            sum+=1ll*(r[2]-r[0])*(r[3]-r[1]);
            mp[{r[0],r[1]}]++;
            mp[{r[0],r[3]}]++;
            mp[{r[2],r[1]}]++;
            mp[{r[2],r[3]}]++;
        }
        if(area!=sum)return false;

        set<pair<int,int>>S;
        S.insert({left[0],left[1]});
        S.insert({right[0],right[1]});
        S.insert({left[0],right[1]});
        S.insert({right[0],left[1]});

        for(auto ding:S){
            if(mp[{ding.first,ding.second}]!=1)return false;
        }
        for(auto r:rs){
            if(S.count({r[0],r[1]}))continue;
            if(S.count({r[2],r[3]}))continue;

            if(mp[{r[0],r[1]}]&1)return false;
            if(mp[{r[2],r[3]}]&1)return false;
        }
        return true;
    }
};
上一篇 下一篇

猜你喜欢

热点阅读