<p>Given an array <code>rectangles</code> where <code>rectangles[i] = [x<sub>i</sub>, y<sub>i</sub>, a<sub>i</sub>, b<sub>i</sub>]</code> represents an axis-aligned rectangle. The bottom-left point of the rectangle is <code>(x<sub>i</sub>, y<sub>i</sub>)</code> and the top-right point of it is <code>(a<sub>i</sub>, b<sub>i</sub>)</code>.</p>

<p>Return <code>true</code> <em>if all the rectangles together form an exact cover of a rectangular region</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perectrec1-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
<strong>Output:</strong> true
<strong>Explanation:</strong> All 5 rectangles together form an exact cover of a rectangular region.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfectrec2-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
<strong>Output:</strong> false
<strong>Explanation:</strong> Because there is a gap between the two rectangular regions.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfecrrec4-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
<strong>Output:</strong> false
<strong>Explanation:</strong> Because two of the rectangles overlap with each other.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rectangles.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>rectangles[i].length == 4</code></li>
	<li><code>-10<sup>5</sup> &lt;= x<sub>i</sub> &lt; a<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>5</sup> &lt;= y<sub>i</sub> &lt; b<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    typedef struct APoint_t {
  int32_t y;
  int32_t x;
} APoint;

typedef struct Box_t {
  APoint topRight;
  APoint bottomLeft;
  APoint topLeft;
  APoint bottomRight;
} Box;

void insert(Box &box, vector<int> &rectangle) {
  if(rectangle[0] < box.bottomLeft.x) {
    box.bottomLeft.x = rectangle[0];
  }
  if(rectangle[1] < box.bottomLeft.y) {
    box.bottomLeft.y = rectangle[1];
  }
  if(rectangle[2] > box.topRight.x) {
    box.topRight.x = rectangle[2];
  }
  if(rectangle[3] > box.topRight.y) {
    box.topRight.y = rectangle[3];
  }

  box.topLeft.y = box.topRight.y;
  box.topLeft.x = box.bottomLeft.x;

  box.bottomRight.y = box.bottomLeft.y;
  box.bottomRight.x = box.topRight.x;
}

Box fromRectangle(vector<int> &rectangle) {
  return (Box) {
    .topRight = (APoint){
      .y = rectangle[3],
      .x = rectangle[2]
    },
    .bottomLeft = (APoint){
      .y = rectangle[1],
      .x = rectangle[0]
    },
    .topLeft = (APoint) {
      .y = rectangle[3],
      .x = rectangle[0]
    },
    .bottomRight = (APoint) {
      .y = rectangle[1],
      .x = rectangle[2]
    }
  };
}

int64_t area(Box &box) {
  return ((int64_t)box.topRight.x - (int64_t)box.bottomLeft.x) * ((int64_t)box.topRight.y - (int64_t)box.bottomLeft.y);
}

uint8_t arePointsEqual(APoint &a, APoint &b) {
  return memcmp(&a, &b, sizeof(APoint)) == 0;
}

uint8_t doBoxesHaveACommonPoint(Box &a, Box &b) {
  return arePointsEqual(a.bottomLeft, b.bottomLeft) +
         arePointsEqual(a.bottomRight, b.bottomRight) +
         arePointsEqual(a.topLeft, b.topLeft) +
         arePointsEqual(a.topRight, b.topRight);
}

vector<pair<int32_t, int32_t> > boxToPairs(Box &box) {
  vector<pair<int32_t, int32_t> > response;
  response.push_back(make_pair(box.bottomLeft.y, box.bottomLeft.x));
  response.push_back(make_pair(box.bottomRight.y, box.bottomRight.x));
  response.push_back(make_pair(box.topLeft.y, box.topLeft.x));
  response.push_back(make_pair(box.topRight.y, box.topRight.x));
  return response;
}

uint8_t findHashMatches(vector<vector<int>>& rectangles, Box &edge) {
  map<pair<int32_t, int32_t>, int32_t> mapMemory;
  for(int32_t i = 0, c = rectangles.size(); i < c; i++) {
    Box currentBox = fromRectangle(rectangles[i]);
    vector<pair<int32_t, int32_t> > pairsBoxes = boxToPairs(currentBox);
    for(uint8_t j = 0; j < pairsBoxes.size(); j++) {
      mapMemory[pairsBoxes[j]]++;
    }
  }
  int32_t edges = 0;
  for(auto &it : mapMemory) {
    if(it.second == 1) {
      edges++;
      continue;
    }
    if(it.second % 2) {
      return 0;
    }
  }
  vector<pair<int32_t, int32_t> > pairsBoxes = boxToPairs(edge);
  for(int8_t i = 0; i < pairsBoxes.size(); i++) {
    if(mapMemory[pairsBoxes[i]] != 1) {
      return 0;
    }
  }
  return edges == 4;
}

bool isRectangleCover(vector<vector<int>>& rectangles) {
  if(!rectangles.size()) {
    return false;
  }
  Box box = fromRectangle(rectangles[0]);
  int64_t totalArea = area(box);
  for(int32_t i = 1, c = rectangles.size(); i < c; i++) {
    Box currentBox = fromRectangle(rectangles[i]);
    insert(box, rectangles[i]);
    totalArea += area(currentBox);
  }
  return totalArea == area(box) && findHashMatches(rectangles, box);
}
};
43700