Thủ thành
Xem dạng PDFHình chữ nhật không được bảo vệ lớn nhất
Xét bảng ô vuông kích thước ~w \times h~, gồm ~w~ cột và ~h~ hàng. Có ~n~ ô chứa tháp tại các vị trí ~\left(x_1, y_1\right), \left(x_2, y_2\right), \dots, \left(x_n, y_n\right)~.
Một ô ~\left(x, y\right)~ được gọi là được bảo vệ nếu tồn tại một tháp ~\left(x_i, y_i\right)~ sao cho ~x = x_i~ hoặc ~y = y_i~.
Bảo đảm rằng với mọi ~i \ne j~ thì ~x_i \ne x_j~ và ~y_i \ne y_j~.
Yêu cầu
Tìm diện tích lớn nhất của một hình chữ nhật song song với các cạnh của bảng sao cho mọi ô nằm trong hình chữ nhật đó đều không được bảo vệ.
Dữ liệu
Dòng đầu tiên chứa ba số nguyên ~w, h, n~.
~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i, y_i~.
Kết quả
In ra một số nguyên duy nhất là diện tích lớn nhất của một hình chữ nhật chỉ gồm các ô không được bảo vệ.
Ví dụ
Ví dụ 1
Input
15 8 3
3 8
11 2
8 6
Output
12
Giải thích
Ví dụ 1
Các cột có tháp là ~3, 8, 11~, nên đoạn liên tiếp dài nhất gồm các cột không được bảo vệ có độ dài ~4~.
Các hàng có tháp là ~2, 6, 8~, nên đoạn liên tiếp dài nhất gồm các hàng không được bảo vệ có độ dài ~3~.
Vì vậy diện tích lớn nhất là ~4 \times 3 = 12~.
Ràng buộc và chấm điểm
Ràng buộc
~1 \le w, h \le 40000~
~0 \le n \le \min(w, h)~
~1 \le x_i \le w~
~1 \le y_i \le h~
Với mọi ~i \ne j~, ta có ~x_i \ne x_j~ và ~y_i \ne y_j~.
Chấm điểm
Subtask 1 (100%): Không có ràng buộc bổ sung.
Bình luận