/*
* @lc app=leetcode id=850 lang=cpp
*
* [850] Rectangle Area II
*
* https://leetcode.com/problems/rectangle-area-ii/description/
*
* algorithms
* Hard (45.33%)
* Likes: 213
* Dislikes: 23
* Total Accepted: 8K
* Total Submissions: 17.5K
* Testcase Example: '[[0,0,2,2],[1,0,2,3],[1,0,3,1]]'
*
* We are given a list of (axis-aligned) rectangles. Each rectangle[i] = [x1,
* y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner,
* and (x2, y2) are the coordinates of the top-right corner of the ith
* rectangle.
*
* Find the total area covered by all rectangles in the plane. Since the
* answer may be too large, return it modulo 10^9 + 7.
*
*
*
* Example 1:
*
*
* Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
* Output: 6
* Explanation: As illustrated in the picture.
*
*
* Example 2:
*
*
* Input: [[0,0,1000000000,1000000000]]
* Output: 49
* Explanation: The answer is 10^18 modulo (10^9 + 7), which is (10^9)^2 =
* (-7)^2 = 49.
*
*
* Note:
*
*
* 1 <= rectangles.length <= 200
* rectanges[i].length = 4
* 0 <= rectangles[i][j] <= 10^9
* The total area covered by all rectangles will never exceed 2^63 - 1 and thus
* will fit in a 64-bit signed integer.
*
*/
class Solution {
public:
class Point {
public:
int x, y, val;
Point(int x, int y, int val): x(x), y(y), val(val) {}
};
int rectangleArea(vector<vector<int>>& rectangles) {
const int M = 1000000007;
vector<Point> points;
for (const auto &r : rectangles) {
points.push_back(Point(r[0], r[1], 1));
points.push_back(Point(r[0], r[3], -1));
points.push_back(Point(r[2], r[1], -1));
points.push_back(Point(r[2], r[3], 1));
}
sort(points.begin(), points.end(), [](Point &a, Point &b) {
return a.x < b.x;
});
const auto cal_y = [](map<int, int> &m) {
int res = 0, pre = -1, sum = 0;
for (const auto &p : m) {
if (sum > 0) res += p.first - pre;
sum += p.second;
pre = p.first;
}
return res;
};
map<int, int> m;
const int N = points.size();
int pre_x = -1, pre_y = -1, res = 0;
for (int i = 0; i < N; ++i) {
Point &p = points[i];
if (!m.count(p.y)) m[p.y] = 0;
m[p.y] += p.val;
if (i == N - 1 || points[i + 1].x > p.x) {
if (pre_x > -1) {
res += ((long)pre_y * (p.x - pre_x)) % M;
res %= M;
}
pre_y = cal_y(m);
pre_x = p.x;
}
}
return res;
}
};