P1578 [WC2002] Cow Bath

Because John built a fence around the cow field, the cows became angry and their milk yield dropped sharply. To appease them, John decided to build a large bath inside the field. However, John’s cows have a strange habit: each cow must produce milk at a fixed position in the field, and cows obviously cannot produce milk in the bath. Therefore, John wants the bath not to cover these milking points. Once again, he turns to Clevow for help. Can you help Clevow? John’s field and the planned bath are both rectangles. The bath must lie completely inside the field, and its sides must be parallel to, or coincide with, the sides of the field. The bath must not cover any milking point, but milking points may lie on the boundary of the bath. Clevow of course wants the bath to have the largest possible area, so your task is to compute the maximum possible area of the bath.

The first line contains two integers $L$ and $W$, denoting the length and width of the field. The second line contains an integer $n$, denoting the number of milking points. Each of the following $n$ lines contains two integers $x$ and $y$, denoting the coordinates of a milking point.

Output a single line containing an integer $S$, the maximum area of the bath.

For all testdata, $0 \le n \le 5 \times 10^3$, $1 \le L, W \le 3 \times 10^4$. All milking points lie within the field, i.e., $0 \le x \le L$, $0 \le y \le W$. Thanks to @凯瑟琳98 for providing 4 sets of hack testdata. Translated by ChatGPT 5