Thủ thành

Xem dạng PDF

Gửi bài giải

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

Dạng bài

Hì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

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.