Chọn ĐTQG ĐHSPHN 2026 - Giải phóng mặt bằng

Xem dạng PDF

Gửi bài giải

Điểm: 70,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trê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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.