JOI 2014/2015 본선 5- IOI 왕국 > 문제은행 : 정보올림피아드&알고리즘




2945 : IOI 왕국

제한시간
5000 ms   
메모리제한
512 MB   
해결횟수
3 회   
시도횟수
8 회   

문제

역사학자인 KOI 교수는 이전에 존재했던 IOI 왕국에 대해 연구하고 있다.
과거의 조사에 따르면, IOI 왕국은 세로 H 크기에 가로 W 크기이며, IOI 왕국의 수도는 방어를 위해 성벽으로 둘러싸여 있었다.


IOI 왕국의 수도를 둘러싸는 성벽은 다음과 같은 형태를 하고 있다:

- 성벽의 크기 s(s ≥ 3)가 있다.
- 크기 s의 성벽은 s × s의 정사각형 영역에서 안의 (s-2) × (s-2) 정사각형 영역을 제외한 테두리 모양을 하고 있다.

 

또 다른 조사에 의하면, 수도를 둘러싼 성벽의 크기는 L 이상이었다. 그리고 어떤 칸들에는 오래된 나무가 있는데, 나무가 있는 위치에는 성벽이 존재하지 않았음을 알고 있다.


KOI 교수는 이러한 사실들을 바탕으로 있을 수 있는 성벽의 가지 수를 알고 싶어한다. 이 때, 성벽의 크기가 같더라도 위치가 다르면 서로 다른 성벽으로 간주한다.


IOI 왕국의 크기와, 성벽의 최소 크기, 그리고 나무의 위치들이 주어졌을 때 가능한 성벽의 가지 수를 구하는 프로그램을 작성하시오.


입력형식

입력의 첫 줄에는 정수 H, W, L, P가 공백으로 구분되어 주어진다. 이는 IOI 왕국의 크기가 세로 H, 가로 W이며 성벽의 최소 크기는 L, 나무의 개수가 P라는 뜻이다. 다음 P 개의 줄에 나무의 위치가 Ai, Bi가 공백으로 구분되어 주어진다. 이는 나무가 Ai번째 줄, Bi번째 칸에 있음을 의미한다. 그리고 다음 제약 사항을 만족한다: 1 <= H, W <= 4 000 3 <= L <= min(H, W) 0 <= P <= 100,000 1 <= Ai <= H (1 <= i <=P) 1 <= Bi <= W (1 <= i <= P) (Ai, Bi) != (Aj, Bj) (1 <= i < j <= P)

출력형식

첫 줄에 가능한 성벽의 가지 수를 출력한다.

입력 예

5 5 3 2
2 2
4 3

출력 예

4

입력 예

7 8 4 3
2 2
3 7
6 5

출력 예

13

입력 예

4000 4000 1234 4
1161 3028
596 1892
3731 2606
702 1530

출력 예

7050792912

Hint!

1번 예제에서 가능한 성벽은 아래 4가지이다. 나무는 x로 표시되어있다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP