가장 큰 정사각형

시간 제한2초메모리 제한128 MB

요약

N×N 격자에서 나쁜 칸 W개의 위치가 주어질 때, 나쁜 칸을 L개 이하로 포함하는 가장 큰 정사각형을 찾는다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 누적 합, 투 포인터, 완전 탐색
정답자: 아직 제출이 없습니다

문제

$N \times N$ 크기의 정사각형 태양전지 모자이크가 있다 ( $1 \le N \le 2000$ ). 각 태양전지는 정상이거나 불량이다. 불량인 전지는 $W$ 개 있다 ( $1 \le W \le 50000$ ). 이 모자이크 안에서, 불량 전지를 최대 $L$ 개 ( $0 \le L \le W$ ) 포함하는 가장 큰 정사각형을 찾아야 한다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 $Z$ ( $Z \le 20$ )가 홀로 주어진다. 이어서 $Z$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공백으로 구분된 세 정수 $N$ , $W$ , $L$ 이 주어진다. 그 다음 $W$ 개의 줄에는 각각 공백으로 구분된 두 정수가 주어지며, 불량 태양전지가 있는 위치의 행과 열(각각 $1$ 이상 $N$ 이하)을 나타낸다.

출력

각 입력 사례에 대해, 불량 태양전지를 최대 $L$ 개 포함하는 가장 큰 정사각형의 넓이를 정수 하나로 출력한다.

힌트

모자이크가 $4 \times 4$ 이고, 정상('G')과 불량('B') 전지가 다음과 같이 배치되어 있다고 하자.

BGGG
GBBG
GGGG
GGGG

아래쪽의 여러 $2 \times 2$ 정사각형은 불량 전지를 하나도 포함하지 않지만, 모든 $3 \times 3$ 정사각형은 적어도 두 개의 불량 전지를 포함한다.

예제3

예제 1
입력
```
1
4 3 1
1 1
2 2
2 3
```
예상 출력
```
4
```
예제 2
입력
```
1
4 3 0
1 1
2 2
2 3
```
예상 출력
```
4
```
예제 3
입력
```
1
5 4 4
1 1
1 5
5 1
5 5
```
예상 출력
```
25
```