#P1578. Maximal Bathhouse Area
Maximal Bathhouse Area
Maximal Bathhouse Area
John built a rectangular cattle ranch, but his cows are upset because their milk production points, fixed at certain locations in the farm, are affected. To make peace with the cows, John plans to construct a rectangular bathhouse inside the farm. The bathhouse must satisfy the following conditions:
- The bathhouse is a rectangle that lies completely within the farm.
- The edges of the bathhouse are parallel (or coincide) with the edges of the farm.
- The bathhouse must not cover (i.e. have in its strict interior) any milk production point. However, a milk production point is allowed to lie exactly on the boundary of the bathhouse.
Your task is to compute the maximum area of such a bathhouse.
Mathematically, if a candidate bathhouse has its left and right boundaries at xL and xR, and bottom and top boundaries at yB and yT, then its area is given by:
[ Area = (x_R - x_L) \times (y_T - y_B), ]
with the condition that for every milk production point \((x, y)\), it must hold that either \(x \le x_L\), \(x \ge x_R\), \(y \le y_B\), or \(y \ge y_T\), or the point lies exactly on the boundary (i.e. \(x = x_L\), \(x = x_R\), \(y = y_B\), or \(y = y_T\)).
inputFormat
The input consists of the following:
- The first line contains two integers
W
andH
(1 ≤ W, H ≤ 109) representing the width and height of the farm. The bottom-left corner of the farm is assumed to be at (0, 0) and the top-right corner at (W, H). - The second line contains an integer
n
(1 ≤ n ≤ 1000) representing the number of milk production points. - Each of the following
n
lines contains two integersx
andy
(0 ≤ x ≤ W, 0 ≤ y ≤ H) specifying the coordinates of a milk production point.
Note: A milk production point can lie on the boundary of the farm.
outputFormat
Output a single integer, the maximum area of a bathhouse satisfying the above conditions.
sample
10 10
1
5 5
50