PreVOI 2024 - Bức ảnh
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Alice đã dán một số bức ảnh hình chữ nhật lên bức tường trong phòng làm việc. Mỗi lần dán, Alice luôn dán sao cho các cạnh của bức ảnh song song với trục ngang hoặc dọc của bức tường và ghi lại tọa độ trái dưới, phải trên của bức ảnh. Mỗi bức ảnh có thể bị che một phần hoặc bị che toàn bộ bởi các bức ảnh khác. Nếu chỉ quan tâm đến những phần phủ lên bức tường thì các bức ảnh tạo thành những hình ảnh độc đáo. Sau lúc làm việc căng thẳng, Alice nhìn lên bức tường và tự hỏi, tổng độ dài đường biên của các hình tạo thành là bao nhiêu.

Yêu cầu: Cho vị trí dán của ~n~ bức ảnh, hãy tính tổng độ đường biên của các hình tạo thành.
Input
Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~ là số bức ảnh được dán lên tường;
Dòng thứ ~i~ ~(1 \le i \le n)~ chứa bốn số nguyên ~x_i, y_i, u_i, v_i~ ~(-10^9 \le x_i < u_i \le 10^9; -10^9 \le y_i < v_i \le 10^9)~, trong đó ~x_i, y_i~ là tọa độ trái dưới và ~u_i, v_i~ là tọa độ phải trên của hình chữ nhật mô tả bức ảnh được dán lên tường.
Output
- Ghi ra một số nguyên là tổng độ dài đường biên của các hình tạo thành.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~n \le 100~ và ~\lvert x_i\rvert, \lvert y_i\rvert, \lvert u_i\rvert, \lvert v_i\rvert \le 10^2~ |
| 2 | ~40\%~ | ~n \le 5000~ và ~\lvert x_i\rvert, \lvert y_i\rvert, \lvert u_i\rvert, \lvert v_i\rvert \le 10^4~ |
| 3 | ~30\%~ | Không có giới hạn gì thêm |
Sample Input 1
4
0 1 1 2
1 0 2 1
2 1 3 2
1 2 2 3
Sample Output 1
16
Sample Input 2
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
Sample Output 2
228
Bình luận