What's a good algorithm for Defense of a Kingdom?

Question

I was trying to Solve the Defense of a Kingdom problem and came up with an algorithm but it exceeds the time limit of the problem.

I want to know a good algorithm to solve this within the time limit.

The problem:

Theodore implements a new strategy game “Defense of a Kingdom”. On each level a player defends the Kingdom that is represented by a rectangular grid of cells. The player builds crossbow towers in some cells of the grid. The tower defends all the cells in the same row and the same column. No two towers share a row or a column.

The penalty of the position is the number of cells in the largest undefended rectangle. For example, the position shown on the picture has penalty 12.

Help Theodore write a program that calculates the penalty of the given position.

Input

The first line of the input file contains the number of test cases.

Each test case consists of a line with three integer numbers: w — width of the grid, h — height of the grid and n — number of crossbow towers (1 ≤ w, h ≤ 40 000; 0 ≤ n ≤ min(w, h)).

Each of the following n lines contains two integer numbers xi and yi — the coordinates of the cell occupied by a tower (1 ≤ xi ≤ w; 1 ≤ yi ≤ h).

Output

For each test case, output a single integer number — the number of cells in the largest rectangle that is not defended by the towers.

Example

Input:
1
15 8 3
3 8
11 2
8 6

Output: 12

Answer 1

I would do it like this:

Given w, h as width and height of the playing field, and the coordinates of the towers as (x1,y1) .. (xN,yN), split the coordinates into two lists x1..xN, y1..yN, sort both of those coordinate lists.

Then calculate the empty spaces, e.g. dx[] = { x1, x2-x1, ..., xN - xN-1, (w + 1) - xN }. Do the same for the y coordinates: dy[] = { y1, y2-y1, ..., yN - yN-1, (h + 1) - yN }. Multiply max(dx)-1 by max(dy)-1 and you should have the largest uncovered rectangle. You have to decrement the delta values by one because the line covered by the higher coordinate tower is included in it, but it is not uncovered.

Answer 2

It is easy to see that the set of undefended cells is cartesian product of undefended “holes” in level's walls. So, at first, you don't need to store the whole field in memory — storing just two sequences of towers' coordinates will be enough.

The second observation would be that in final field, with all the towers set up, the largest undefended rectangle is equal to cartesian product of two most wide wall holes. Hence its area is equal to product of the holes' lengths. So what we really need to do is to find two most wide wall holes (one on x axis, one on y), and multiply their lengths. That would be the answer.

The final note is about input. The towers will probably be shuffled in some way around; but we need a way to derive all holes' lengths. This can easily be done by first sorting the coordinate sequences, separately one and the other, and then calculating {x_i+1−x_i} and {y_i+1−y_i} in a single pass. In the same pass we can even find the maximums — multiply them, and you are done.