Hợp Các Hình Chữ Nhật
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Trên bản đồ quy hoạch đô thị có $N$ khu đất hình chữ nhật có các cạnh song song với hai trục tọa độ. Các khu đất có thể chồng lấn lên nhau.
Sử dụng thuật toán đường quét (Sweep Line) kết hợp Segment Tree, hãy tính tổng diện tích phần mặt phẳng được phủ bởi ít nhất một hình chữ nhật.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
- $N$ dòng tiếp theo, mỗi dòng chứa $4$ số nguyên $x_1, y_1, x_2, y_2$ ($x_1 \le x_2, y_1 \le y_2$) mô tả hình chữ nhật có góc dưới-trái $(x_1, y_1)$ và góc trên-phải $(x_2, y_2)$.
Dữ liệu ra
- In ra một số nguyên là tổng diện tích phần hợp của các hình chữ nhật.
Ví dụ
| Input | Output |
|---|---|
| 3 0 0 4 4 2 2 6 6 1 1 3 3 |
28 |
Giới hạn
- $1 \le N \le 10^5$
- $|x_i|, |y_i| \le 10^9$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion