C++ Is it enough to check "unpaired vertices == 4" only?


  • 2
    A

    First there shouldn't be identical vertices (overlapping).
    Then all paired vertices should make up either an edge (2 adjacent) or a plane (4 adjacent).
    So there should be, and must be, exactly 4 vertices not paired since they are the 4 corners of the perfect rectangle.

    Is this condition alone strong enough? Seems legit. Any counter testcases?

    46 / 46 test cases passed
    Status: Accepted
    Runtime: 139 ms
    Beats 99.82%

    class Solution {
    public:
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            unordered_map<unsigned long long, uint> map;
            map.reserve(rectangles.size()*4);
            for (auto& rec : rectangles) {
                unsigned long long xy[4];
                xy[0]= (unsigned long long)rec[0] << 32 | (uint)rec[1];
                xy[1]= (unsigned long long)rec[0] << 32 | (uint)rec[3];
                xy[2]= (unsigned long long)rec[2] << 32 | (uint)rec[3];
                xy[3]= (unsigned long long)rec[2] << 32 | (uint)rec[1];
                for (uint i = 0; i < 4; i++)  {
                    uint pos = 1 << i; //1 Left Bottom, 2 Left Top, 4 Right Top, 8 Right Bottom
                    uint& val = map[xy[i]];
                    if (val & pos) return false;
                    else val |= pos;
                }
            }
            uint cnt = 0;
            for (auto& p : map) {
                uint pos = p.second;
                if (!(pos == 1+2 || pos == 2+4 || pos == 4+8 || pos == 8+1 || pos == 1+2+4+8) && ++cnt > 4) return false;
            }
            return cnt == 4;
        }
    };
    

  • 0
    H

    Great solution, liked your corner identification trick.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.