Hợp Các Hình Chữ Nhật

Buổi 61 — Hình học tính toán
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề 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
Draft saved