c++ - 什么是保卫王国的好算法？

Question

我试图解决 Defense of a Kingdom 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

我会这样做:

给定 w，h 作为运动场的宽度和高度，塔的坐标为 (x1,y1) .. (xN, yN)，将坐标分成两个列表 x1..xN，y1..yN，对这两个坐标列表进行排序。

然后计算空格，例如dx[] = { x1, x2-x1, ..., xN - xN-1, (w + 1) - xN }。对 y 坐标执行相同操作:dy[] = { y1, y2-y1, ..., yN - yN-1, (h + 1) - yN }。将 max(dx)-1 乘以 max(dy)-1，您应该得到最大的未覆盖矩形。您必须将 delta 值减一，因为更高坐标塔覆盖的线包含在其中，但未被覆盖。