Informatica Online Judge

  [2032 / 07F0]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 4   Total Tried : 10


The Champion of this Problem (C++) : gs18070 - 24ms / 4330byte
My Best Submission (C++) : N/A

[IOI 2007 - Zagreb, Croatia]

Background

미르코와 슬라브코는 동물 모양의 장난감을 갖고 놀고 있다. 노는 방법은 다음과 같다. 먼저 아래 그림과 같은 세 개의 게임판(1~3차원 칸으로 된 균일 간격 격자) 중 하나를 고른다. 그리고 게임판 내부 임의의 칸(그림에서 동그라미로 표현된)에 N개의 동물 장난감을 집어넣는다.



그림에서 보다시피 어떤 칸에서 인접한 칸은 각 차원의 축과 평행한 선분으로만 연결되어 있는데, 두 칸의 ‘거리’는 다른 칸으로 가기 위해 거쳐야 하는 선분의 최소 개수로 정의된다. 다시 말해 3차원을 예로 들 때 임의의 위치에 있는 칸 A(x1, y1, z1)와 B(x2, y2, z2)의 거리는 단순히 |x1-x2|+|y1-y2|+|z1-z2|가 되며, 2차원이나 1차원의 경우도 같은 계산법이 성립한다는 뜻이다.

게임판에서 서로 거리가 D 이하인 칸에 있는 두 동물은 울음소리를 통해 상대방을 알아차릴 수 있다. 슬라브코는 이렇게 서로 알아차릴 수 있는 동물의 쌍이 얼마나 되는지 알고 싶어한다.

게임판의 종류, 그 게임판에 있는 모든 동물들의 위치와 최장 가청 거리 D 값을 입력 받아 서로 충분히 가까이 있는 동물의 쌍이 얼마나 있는지 찾는 프로그램을 작성하시오.

Input

첫째 줄에는 네 개의 정수가 들어있으며 의미는 순서대로 다음과 같다.

* 게임판의 종류(차원) B (1≤B≤3)
* 동물 개체수 N (1≤N≤100,000)
* 최장 가청 거리 D (1≤D≤100,000,000)
* 게임판 크기 M (동물의 각 축 좌표가 가질 수 있는 최대 크기)

B=1일 때는 M은 최대 75,000,000이며 B=2일 때는 최대 75,000이다. B=3일 때는 최대 75이다.

다음 N개의 줄에는 각 줄마다 동물의 위치 좌표를 나타내는 정수가 B개 들어있다. 정수의 범위는 1 이상 M 이하이다. 한 칸에 두 마리 이상의 동물이 겹쳐 있을 수도 있다.

테스트 케이스 중 전체의 30점에 해당하는 케이스는 N의 값이 최대 1000이다. 그리고 1, 2, 3차원 중 단 한 경우에 대해서라도 완벽하게 문제를 풀면 최소한 30점 이상을 받을 수 있다.

Output

최장 가청 거리 이내에 있는 동물의 쌍수를 출력한다. 64비트 정수를 사용하도록 한다.

IO Example

입력1
1 6 5 100
25
50
50
10
20
23

출력1
4

입력2
2 5 4 10
5 2
7 2
8 4
6 5
4 4

출력2
8

입력3
3 8 10 20
10 10 10
10 10 20
10 20 10
10 20 20
20 10 10
20 10 20
20 20 10
20 20 20

출력3
12

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]