rectangle_union_area.hpp¶
Exact union area of half-open axis-aligned integer rectangles by a sweep line and covered-length segment tree in O(n log n).
Verified by area_of_union_of_rectangles.
精确计算多个半开轴对齐整数矩形的并面积；适合覆盖面积需要去除重叠的题目。
Implementation¶
#ifndef NOYA_RECTANGLE_UNION_AREA_HPP
#define NOYA_RECTANGLE_UNION_AREA_HPP 1
/// @complexity Time: O(n log n).
/// Space: O(n).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Exact union area of half-open axis-aligned integer rectangles by a
/// sweep line and covered-length segment tree in O(n log n).
inline __int128 rectangle_union_area(
const std::vector<std::array<std::int64_t, 4>> &rectangles) {
struct event {
std::int64_t x;
std::int64_t lower;
std::int64_t upper;
int delta;
};
std::vector<event> events;
std::vector<std::int64_t> coordinates;
for (auto [left, right, lower, upper] : rectangles) {
assert(left <= right && lower <= upper);
if (left == right || lower == upper) {
continue;
}
events.push_back({left, lower, upper, 1});
events.push_back({right, lower, upper, -1});
coordinates.push_back(lower);
coordinates.push_back(upper);
}
if (events.empty()) {
return 0;
}
std::sort(events.begin(), events.end(),
[](const event &a, const event &b) { return a.x < b.x; });
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
int interval_count = int(coordinates.size()) - 1;
std::vector<int> cover(interval_count * 4 + 4);
std::vector<__int128> length(interval_count * 4 + 4);
auto pull = [&](int node, int left, int right) {
if (cover[node] > 0) {
length[node] = __int128(coordinates[right]) - coordinates[left];
} else if (right - left == 1) {
length[node] = 0;
} else {
length[node] = length[node * 2] + length[node * 2 + 1];
}
};
auto update = [&](auto &self, int node, int left, int right, int query_left,
int query_right, int delta) -> void {
if (query_right <= left || right <= query_left) {
return;
}
if (query_left <= left && right <= query_right) {
cover[node] += delta;
pull(node, left, right);
return;
}
int middle = std::midpoint(left, right);
self(self, node * 2, left, middle, query_left, query_right, delta);
self(self, node * 2 + 1, middle, right, query_left, query_right, delta);
pull(node, left, right);
};
__int128 area = 0;
std::int64_t previous_x = events[0].x;
for (int index = 0; index < int(events.size());) {
std::int64_t current_x = events[index].x;
area += (__int128(current_x) - previous_x) * length[1];
while (index < int(events.size()) && events[index].x == current_x) {
int lower = int(std::lower_bound(coordinates.begin(), coordinates.end(),
events[index].lower) -
coordinates.begin());
int upper = int(std::lower_bound(coordinates.begin(), coordinates.end(),
events[index].upper) -
coordinates.begin());
update(update, 1, 0, interval_count, lower, upper, events[index].delta);
index++;
}
previous_x = current_x;
}
return area;
}
} // namespace noya
#endif // NOYA_RECTANGLE_UNION_AREA_HPP
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>
/// @complexity Time: O(n log n).
/// Space: O(n).
namespace noya {
/// @brief Exact union area of half-open axis-aligned integer rectangles by a
/// sweep line and covered-length segment tree in O(n log n).
inline __int128 rectangle_union_area(
const std::vector<std::array<std::int64_t, 4>> &rectangles) {
struct event {
std::int64_t x;
std::int64_t lower;
std::int64_t upper;
int delta;
};
std::vector<event> events;
std::vector<std::int64_t> coordinates;
for (auto [left, right, lower, upper] : rectangles) {
assert(left <= right && lower <= upper);
if (left == right || lower == upper) {
continue;
}
events.push_back({left, lower, upper, 1});
events.push_back({right, lower, upper, -1});
coordinates.push_back(lower);
coordinates.push_back(upper);
}
if (events.empty()) {
return 0;
}
std::sort(events.begin(), events.end(),
[](const event &a, const event &b) { return a.x < b.x; });
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
int interval_count = int(coordinates.size()) - 1;
std::vector<int> cover(interval_count * 4 + 4);
std::vector<__int128> length(interval_count * 4 + 4);
auto pull = [&](int node, int left, int right) {
if (cover[node] > 0) {
length[node] = __int128(coordinates[right]) - coordinates[left];
} else if (right - left == 1) {
length[node] = 0;
} else {
length[node] = length[node * 2] + length[node * 2 + 1];
}
};
auto update = [&](auto &self, int node, int left, int right, int query_left,
int query_right, int delta) -> void {
if (query_right <= left || right <= query_left) {
return;
}
if (query_left <= left && right <= query_right) {
cover[node] += delta;
pull(node, left, right);
return;
}
int middle = std::midpoint(left, right);
self(self, node * 2, left, middle, query_left, query_right, delta);
self(self, node * 2 + 1, middle, right, query_left, query_right, delta);
pull(node, left, right);
};
__int128 area = 0;
std::int64_t previous_x = events[0].x;
for (int index = 0; index < int(events.size());) {
std::int64_t current_x = events[index].x;
area += (__int128(current_x) - previous_x) * length[1];
while (index < int(events.size()) && events[index].x == current_x) {
int lower = int(std::lower_bound(coordinates.begin(), coordinates.end(),
events[index].lower) -
coordinates.begin());
int upper = int(std::lower_bound(coordinates.begin(), coordinates.end(),
events[index].upper) -
coordinates.begin());
update(update, 1, 0, interval_count, lower, upper, events[index].delta);
index++;
}
previous_x = current_x;
}
return area;
}
} // namespace noya