Hướng giải của Diện tích hợp hình chữ nhật
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Hướng dẫn giải
Dùng thuật toán đường quét (sweep line) kết hợp cây phân đoạn (segment tree) với nén toạ độ (coordinate compression). Ý tưởng: quét một đường thẳng đứng từ trái sang phải. Tại mỗi sự kiện (cạnh trái / cạnh phải), cập nhật trạng thái các đoạn \(y\) đang được phủ trên cây phân đoạn, sau đó cộng diện tích bằng chiều rộng giữa hai sự kiện nhân với tổng chiều dài các đoạn \(y\) đang được phủ.
Độ phức tạp: \(O(N \log N)\).
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
struct Event {
long long x, y1, y2, type;
Event(long long x, long long y1, long long y2, long long type) : x(x), y1(y1), y2(y2), type(type) {}
bool operator<(const Event& o) const { return x < o.x; }
};
struct SegTree {
int n;
vector<long long> cnt, len;
vector<long long> ys;
SegTree(vector<long long>& ys) : ys(ys) {
n = ys.size() - 1;
cnt.assign(4 * n, 0);
len.assign(4 * n, 0);
}
void update(int l, int r, long long val, int id, int L, int R) {
if (l >= R || r <= L) return;
if (l <= L && R <= r) {
cnt[id] += val;
} else {
int M = (L + R) / 2;
update(l, r, val, id * 2, L, M);
update(l, r, val, id * 2 + 1, M, R);
}
if (cnt[id]) len[id] = ys[R] - ys[L];
else if (R - L == 1) len[id] = 0;
else len[id] = len[id * 2] + len[id * 2 + 1];
}
void update(int l, int r, long long val) { update(l, r, val, 1, 0, n); }
long long total() { return len[1]; }
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n; cin >> n;
vector<Event> events;
vector<long long> ys;
for (int i = 0; i < n; i++) {
long long x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
events.emplace_back(x1, y1, y2, 1);
events.emplace_back(x2, y1, y2, -1);
ys.push_back(y1); ys.push_back(y2);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
sort(events.begin(), events.end());
SegTree st(ys);
long long ans = 0;
long long prev_x = events[0].x;
for (auto& e : events) {
long long cur_x = e.x;
ans += st.total() * (cur_x - prev_x);
int l = lower_bound(ys.begin(), ys.end(), e.y1) - ys.begin();
int r = lower_bound(ys.begin(), ys.end(), e.y2) - ys.begin();
st.update(l, r, e.type);
prev_x = cur_x;
}
cout << ans << "\n";
return 0;
}
Nhận xét