2. LQDOJ Cup 2025 - Round #5 - Diện tích chung lớn nhất
An là một nhà quy hoạch đô thị. Anh ấy có một tấm bản đồ thể hiện \(n\) khu vực được phép xây dựng. Các khu vực này được đánh số từ \(1\) đến \(n\).
Tấm bản đồ này được gắn một hệ tọa độ Descartes. Khu vực được phép xây dựng thứ \(i\) có dạng một hình chữ nhật có các cạnh song song với trục tọa độ, với tọa độ của hai góc đối diện là \((x_1^{(i)}, y_1^{(i)})\) và \((x_2^{(i)}, y_2^{(i)})\).
An đang xem xét \(q\) dự án xây dựng. Các dự án được đánh số từ \(1\) đến \(q\). Trong dự án thứ \(j\), An cần chọn ra một vùng đất nằm trong ít nhất \(k_j\) khu vực được phép xây dựng. An muốn biết diện tích lớn nhất của một vùng đất như vậy. Trong trường hợp không tồn tại \(k_j\) khu vực nào có phần chung, diện tích lớn nhất là \(0\).
Các bạn hãy giúp An tìm diện tích lớn nhất với mỗi dự án.
Dữ liệu
Vào từ file văn bản commonarea.inp:
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \le n \le 333, 1 \le q \le 11)\) – số khu vực được phép xây dựng và số dự án.
- Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(x_1^{(i)}, y_1^{(i)}, x_2^{(i)}, y_2^{(i)}\) \(( -123456789 \le x_1^{(i)}, y_1^{(i)}, x_2^{(i)}, y_2^{(i)} \le 987654321)\) – tọa độ hai góc đối diện của khu vực được phép xây dựng thứ \(i\).
- Dòng cuối cùng chứa \(q\) số nguyên \(k_1, k_2, \ldots, k_q\) \((1 \le k_j \le n)\) – số lượng khu vực trong các dự án.
Kết quả
Ghi ra file văn bản commonarea.out:
In ra một dòng duy nhất chứa \(q\) số nguyên, số thứ \(j\) là diện tích lớn nhất tìm được trong dự án thứ \(j\).
Ràng buộc
Bộ test của bài được chia làm các subtask như sau:
- Subtask \(1\) (\(19\) điểm): \(n \le 22\).
- Subtask \(2\) (\(19\) điểm): \(n \le 33\).
- Subtask \(3\) (\(13\) điểm): \(n \le 66\).
- Subtask \(4\) (\(13\) điểm): \(k_j \ge n - 3\).
- Subtask \(5\) (\(23\) điểm): \(k_j \ge n - 4\).
- Subtask \(6\) (\(13\) điểm): Không có ràng buộc gì thêm.
Ví dụ
Ví dụ 1
commonarea.inp
2 2
0 0 5 5
2 2 7 7
1 2commonarea.out
25 9 Ví dụ 2
commonarea.inp
5 5
0 0 5 5
1 1 4 4
2 0 3 5
0 2 5 3
6 6 7 7
1 2 3 4 5commonarea.out
25 9 3 1 0 Giải thích
Hình vẽ dưới đây mô tả ví dụ thứ nhất:
- Với \(k_1 = 1\), diện tích lớn nhất là diện tích của khu vực \(1\), bằng \(25\).
- Với \(k_2 = 2\), diện tích lớn nhất là phần chung của khu vực \(1\) và \(2\), bằng \(9\).
Hình vẽ dưới đây mô tả ví dụ thứ hai:
- Với \(k_1 = 1\), diện tích lớn nhất là diện tích của khu vực \(1\) (bằng \(25\)).
- Với \(k_2 = 2\), diện tích lớn nhất là phần chung của khu vực \(1\) và \(2\) (bằng \(9\)).
- Với \(k_3 = 3\), diện tích lớn nhất là phần chung của khu vực \(1\), \(2\) và \(3\) (bằng \(3\)).
- Với \(k_4 = 4\), diện tích lớn nhất là phần chung của khu vực \(1\), \(2\), \(3\) và \(4\) (bằng \(1\)).
- Với \(k_5 = 5\), \(5\) khu vực không có phần chung, nên diện tích lớn nhất tìm được là \(0\).