장난감 동물

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

요약

1차원, 2차원, 3차원 정수 격자 위의 점들 중 맨해튼 거리가 D 이하인 쌍의 수를 센다.

난이도: 어려움10점 중 8점
유형: 분할 정복, 정렬, 기하, 비트 연산
정답자: 아직 제출이 없습니다

문제

상근이와 선영이는 장난감 동물을 가지고 논다. 먼저 아래 세 종류의 게임판 중 하나를 고른다. 각 게임판은 여러 개의 칸으로 이루어져 있으며, $1$ 번 게임판은 1차원(직선), $2$ 번은 2차원(격자), $3$ 번은 3차원(입체 격자) 모양이다.

게임판

각 칸은 정수 좌표로 나타내고, 서로 인접한 칸은 선분으로 연결되어 있다.

$1$ 번 게임판: 칸을 좌표 $x$ 로 나타내며, 칸 $x$ 는 칸 $x-1$ , $x+1$ 과 인접하다.
$2$ 번 게임판: 칸을 좌표 $(x, y)$ 로 나타내며, 칸 $(x, y)$ 는 $(x\pm1,\ y)$ , $(x,\ y\pm1)$ 과 인접하다.
$3$ 번 게임판: 칸을 좌표 $(x, y, z)$ 로 나타내며, 칸 $(x, y, z)$ 는 $(x\pm1,\ y,\ z)$ , $(x,\ y\pm1,\ z)$ , $(x,\ y,\ z\pm1)$ 과 인접하다.

상근이는 $N$ 마리의 장난감 동물을 칸에 놓는다. 한 칸에 여러 마리가 놓일 수도 있다.

두 칸 사이의 거리는 한 칸에서 다른 칸까지 가는 데 필요한 최소 이동 횟수이다. 한 번 이동할 때마다 인접한 칸으로 갈 수 있으므로, 두 칸의 거리는 좌표별 차이의 절댓값을 모두 더한 값과 같다.

$1$ 번 게임판: $|x_1 - x_2|$
$2$ 번 게임판: $|x_1 - x_2| + |y_1 - y_2|$
$3$ 번 게임판: $|x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2|$

두 장난감 동물은 둘이 놓인 칸 사이의 거리가 $D$ 이하일 때 서로의 소리를 들을 수 있다. 게임판의 종류, 각 장난감 동물의 위치, 그리고 $D$ 가 주어졌을 때, 서로의 소리를 들을 수 있는 장난감 동물 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 네 정수 $B$ , $N$ , $D$ , $M$ 이 공백으로 구분되어 주어진다.

$B$ 는 게임판의 종류이다. ( $1 \le B \le 3$ )
$N$ 은 장난감 동물의 수이다. ( $1 \le N \le 100\,000$ )
$D$ 는 두 장난감 동물이 서로의 소리를 들을 수 있는 가장 먼 거리이다. ( $1 \le D \le 100\,000\,000$ )
$M$ 은 좌표가 가질 수 있는 최댓값이다. $B = 1$ 이면 $M \le 75\,000\,000$ , $B = 2$ 이면 $M \le 75\,000$ , $B = 3$ 이면 $M \le 75$ 이다.

다음 $N$ 개의 줄에 각 장난감 동물의 좌표가 주어진다. $B$ 번 게임판에서는 한 줄에 정수 $B$ 개가 공백으로 구분되어 주어진다. 즉 $B = 1$ 이면 $x$ , $B = 2$ 이면 $x\ y$ , $B = 3$ 이면 $x\ y\ z$ 가 주어지며, 모든 좌표는 $1$ 이상 $M$ 이하의 자연수이다. 같은 칸에 여러 마리가 놓일 수도 있다.

출력

서로의 소리를 들을 수 있는 장난감 동물 쌍의 개수를 첫째 줄에 출력한다.

예제7

예제 1
입력
```
2 5 4 10
5 2
7 2
8 4
6 5
4 4
```
예상 출력
```
8
```
예제 2
입력
```
1 4 3 100
1
2
5
9
```
예상 출력
```
2
```
예제 3
입력
```
1 5 1 10
3
3
3
3
3
```
예상 출력
```
10
```

예제 4

입력

1 6 100000000 75000000
1
100
50000000
2
75000000
999

예상 출력

예제 5
입력
```
2 4 1 10
1 1
1 2
2 1
2 2
```
예상 출력
```
4
```

예제 6

입력

2 5 100000000 75000
1 1
75000 75000
1 75000
40000 40000
2 3

예상 출력

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