(5 ĐIỂM). DIỆN TÍCH BỊ PHỦ TRÊN MẶT PHẲNG TỌA ĐỘ CHO 𝑛 HÌNH CHỮ...
Bài 3 (5 điểm). Diện tích bị phủ
Trên mặt phẳng tọa độ cho 𝑛 hình chữ nhật đánh số 1, 2, ..., 𝑛. Hình chữ nhật thứ 𝑖 được mô tả
bởi 4 số nguyên
𝑥
𝑖
, 𝑦
𝑖
, 𝑢
𝑖
, 𝑣
𝑖
trong đó (𝑥
𝑖
, 𝑦
𝑖
) là tọa độ của góc dưới - trái còn
(𝑢
𝑖
, 𝑣
𝑖
) là tọa độ
của góc trên-phải.
Hãy tính diện tích của phần mặt phẳng tọa độ bị phủ bởi ít nhất một hình chữ nhật?
Dữ liệu: Vao từ file văn bản AREA.INP
•
Dòng đầu tiên chứa số nguyên dương 𝑛 (𝑛 ≤ 10
5
)
•
𝑛 dòng tiếp theo, dòng thứ 𝑖 chứa bố
n số nguyên 𝑥
𝑖
, 𝑦
𝑖
, 𝑢
𝑖
, 𝑣
𝑖
cách nhau bởi dấu cách có
trị tuyệt đối không vượt quá 10
9
(𝑥
𝑖
< 𝑢
𝑖
, 𝑦
𝑖
< 𝑣
𝑖
)
Kết quả: Một số nguyên duy nhất là diện tích phần mặt phẳng tọa độ bị phủ bởi ít nhất một hình
chữ nhật.
Ví dụ:
AREA.INP
AREA.OUT
2
7
0 0 2 2
1 1 3 3
Ghi chú:
•
Có 40% số test có 𝑛 ≤ 100
, các tọa độ là các số nguyên nằm trong khoảng 0...1000
•
Còn lại có 30% số test có 𝑛 ≤ 10
5
, các tọa độ là các số nguyên trong khoảng 0...1000
•
Còn lại có 20% số test có 𝑛 ≤ 10
5
, các tọa độ là các số nguyên trong khoảng 0...10
5
•
10% số test còn lại không có ràng buộc gì thêm.