가까운 점
시간 제한1초메모리 제한128 MB
최대 15만 개의 3차원 점이 주어질 때 서로 다른 점 사이의 최소 거리의 제곱을 구하고 그 거리를 이루는 쌍의 개수를 세는 문제입니다.
문제
3차원 공간에 점 N개가 주어진다. 서로 다른 두 위치 사이의 거리 중 가장 작은 거리의 제곱과, 그 최단 거리를 이루는 서로 다른 점 쌍의 개수를 구하라.
입력에 같은 좌표가 여러 번 나올 수 있지만, 같은 좌표를 가진 점들은 하나의 점으로 본다.
입력
첫째 줄에 점의 수 N이 주어진다. N은 150,000보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에는 각 점의 좌표 x, y, z가 주어진다. 각 좌표의 절댓값은 1,000,000보다 작거나 같은 정수이다.
같은 좌표를 가진 점은 같은 점으로 취급한다. 입력에는 서로 다른 위치가 적어도 두 개 존재한다.
출력
첫째 줄에 가장 가까운 두 점 사이 거리의 제곱을 출력한다.
둘째 줄에 그 거리의 제곱을 가지는 서로 다른 점 쌍의 개수를 출력한다.
입력은 가장 가까운 두 점 사이 거리의 제곱이 1,000,000,000보다 작은 경우만 주어진다.