Largest Square

Time limit2sMemory limit128 MB

Summary

Given an N by N grid with W bad cells listed explicitly, find the largest axis-aligned square containing at most L bad cells.

Level: Medium7 of 10
Topics: Binary search, Prefix sum, Two pointers, Brute force
Solved: No attempts yet

Problem

There is an $N \times N$ mosaic of square solar cells ( $1 \le N \le 2000$ ). Each solar cell is either good or bad. There are $W$ bad cells ( $1 \le W \le 50000$ ). You must find the largest square within the mosaic that contains at most $L$ ( $0 \le L \le W$ ) bad cells.

Input

The first line of input contains a single integer $Z$ ( $Z \le 20$ ), the number of test cases. The $Z$ test cases then follow.

The first line of a test case contains three space-separated integers $N$ , $W$ , and $L$ . The next $W$ lines each contain two space-separated integers giving the row and column (each from $1$ to $N$ ) of a bad solar cell.

Output

For each input instance, output a single integer: the area of the largest square that contains no more than $L$ bad solar cells.

Hint

Suppose the mosaic is $4 \times 4$ with the following arrangement of good ('G') and bad ('B') cells:

BGGG
GBBG
GGGG
GGGG

Several $2 \times 2$ squares near the bottom contain no bad cells, but every $3 \times 3$ square contains at least two bad cells.

Examples3

Example 1
Input
```
1
4 3 1
1 1
2 2
2 3
```
Expected output
```
4
```
Example 2
Input
```
1
4 3 0
1 1
2 2
2 3
```
Expected output
```
4
```
Example 3
Input
```
1
5 4 4
1 1
1 5
5 1
5 5
```
Expected output
```
25
```