아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

가까운 만유인력

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

요약
각 테스트 케이스마다 거리가 k보다 작은 3차원 점 쌍의 개수를 셉니다.
난이도

보통10점 중 7점

유형
해시맵, 기하
정답자
아직 제출이 없습니다

문제

복잡한 태양계에서 아주 멀리 떨어진 두 물체 사이의 중력은 계산하고 싶지도 않고, 계산해 봐야 무시할 만큼 작아서 컴퓨터만 고생한다. 그래서 거리가 kk보다 가까운 두 물체만 고려하려고 한다.

공간에 점 nn개가 주어질 때, 두 점 사이의 거리가 kk보다 작은 쌍은 몇 개인가?

입력

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 점의 개수 nn과 허용하는 최대 거리 kk가 주어진다. (2≤n≤100,0002 \le n \le 100{,}000, 1≤k≤1091 \le k \le 10^9)

이어지는 nn개의 줄에는 점 하나의 좌표를 나타내는 세 정수 xx, yy, zz가 주어진다. (−109≤x,y,z≤109-10^9 \le x, y, z \le 10^9)

한 테스트 케이스 안에서 같은 점이 두 번 주어지지 않고, 거리가 kk 이하인 점의 쌍은 100,000100{,}000개를 넘지 않는다.

입력의 마지막 줄에는 0이 두 개 주어지며, 이 줄은 테스트 케이스가 아니다.

출력

각 테스트 케이스마다 거리가 kk보다 작은 점의 쌍의 개수를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    7 2
    0 0 0
    1 0 0
    1 2 0
    1 2 3
    1000 1000 1000
    1001 1001 1000
    1001 999 1001
    7 3
    0 0 0
    1 0 0
    1 2 0
    1 2 3
    -1000 1000 -1000
    -1001 1001 -1000
    -1001 999 -1001
    7 4
    0 0 0
    1 0 0
    1 2 0
    1 2 3
    1000 -1000 1000
    1001 -1001 1000
    1001 -999 1001
    0 0
    
    예상 출력
    3
    6
    9