Diện Tích Phủ Sóng
Points
85
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ trạm phát sóng đặt trong khu vực hình chữ nhật. Mỗi trạm thứ $i$ phủ sóng một hình chữ nhật có các cạnh song song với hai trục tọa độ, góc dưới trái tại $(x_{1,i}, y_{1,i})$ và góc trên phải tại $(x_{2,i}, y_{2,i})$.
Hãy tính tổng diện tích phần mặt phẳng được phủ sóng bởi ít nhất một trạm phát sóng.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 50\,000$).
- $N$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$ ($0 \le x_{1,i} < x_{2,i} \le 10^9$, $0 \le y_{1,i} < y_{2,i} \le 10^9$).
Kết quả
- In ra một số nguyên duy nhất là diện tích hợp của $N$ hình chữ nhật.
Subtasks
- Subtask 1 (20%): $N \le 100$, các tọa độ $\le 1000$.
- Subtask 2 (30%): $N \le 2000$.
- Subtask 3 (50%): Không có ràng buộc bổ sung.
Ví dụ
| Input | Output |
|---|---|
| 3 0 0 4 4 2 2 6 6 1 1 3 5 |
29 |
Community Discussion