Chọn ĐTQG ĐHSPHN 2026 - Giải phóng mặt bằng
Xem dạng PDFTrên mặt phẳng tọa độ Descartes có ~m~ mỏ và ~n~ nhà dân. Các mỏ nằm tại những điểm đôi một phân biệt; các nhà cũng nằm tại những điểm đôi một phân biệt. Một mỏ và một nhà có thể trùng vị trí.
Bạn được chọn một hình chữ nhật có các cạnh song song với hai trục tọa độ. Các điểm nằm trên biên hình chữ nhật cũng được tính. Giá trị của hình chữ nhật là
~a \cdot \text{số mỏ trong hình} - b \cdot \text{số nhà trong hình}~.
Hình chữ nhật được phép không chứa điểm nào. Hãy tìm giá trị lớn nhất có thể đạt được.
Input
Dòng đầu chứa số nguyên ~m~ (~1 \le m \le 1000~).
Mỗi dòng trong ~m~ dòng tiếp theo chứa tọa độ một mỏ.
Dòng tiếp theo chứa số nguyên ~n~ (~1 \le n \le 1000~).
Mỗi dòng trong ~n~ dòng tiếp theo chứa tọa độ một nhà.
Dòng cuối chứa hai số nguyên dương ~a~ và ~b~ (~1 \le a,b \le 10^9~).
Mỗi tọa độ là một số nguyên có trị tuyệt đối không quá ~10^9~.
Output
In ra giá trị lớn nhất của một hình chữ nhật hợp lệ.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~m,n \le 10~, trị tuyệt đối tọa độ không quá ~10~ |
| 2 | ~20\%~ | ~m,n \le 100~, trị tuyệt đối tọa độ không quá ~100~ |
| 3 | ~20\%~ | ~m,n \le 100~ |
| 4 | ~40\%~ | Không có giới hạn gì thêm |
Sample Input 1
3
0 0
1 1
2 0
2
1 0
3 3
5 4
Sample Output 1
11
Notes
Chọn hình chữ nhật có hai góc đối diện ~(0,0)~ và ~(2,1)~. Hình chứa cả ba mỏ và một nhà, nên có giá trị ~3 \cdot 5-1 \cdot 4=11~.
Bình luận