가장 가까운 두 별
골드 III의견: 0
천체 관측소가 밤하늘 사진에서 \(N\)개의 별의 평면 좌표 \((x_i, y_i)\)를 추출했다. 두 별이 너무 가까우면 망원경으로 분해할 수 없으므로, 가장 가까운 두 별 사이의 거리를 알아야 한다.
실수 오차를 피하기 위해, 가장 가까운 두 별 사이 거리의 제곱을 출력한다. 즉 모든 별 쌍 \(\{i, j\}\) 중 \((x_i - x_j)^2 + (y_i - y_j)^2\) 의 최솟값을 구하여라.
\(2 \le N \le 200{,}000\). 좌표가 완전히 같은 별이 존재할 수 있으며, 이 경우 거리 제곱은 0이다.
첫째 줄에 별의 수 \(N\)이 주어진다. 이어 \(N\)개의 줄에 각각 두 정수 \(x_i\), \(y_i\)가 주어진다 (\(-10^8 \le x_i, y_i \le 10^8\)). 같은 좌표의 별이 둘 이상 있을 수 있다.
가장 가까운 두 별 사이 거리의 제곱을 한 줄에 출력한다.
4
0 0
5 5
1 1
10 0
2\((0,0)\) 과 \((1,1)\) 사이의 거리 제곱이 \(1^2+1^2=2\) 로 가장 작다.
2
3 4
0 0
25별이 둘뿐이므로 그 거리 제곱 \(3^2+4^2=25\) 가 정답이다.
riseoj 작성
출처 Original
평가 및 의견
가장 가까운 두 별
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
가장 가까운 두 별