가장 가까운 두 점
플래티넘 IV의견: 0
\(2\)차원 평면 위에 \(N\)개의 점이 주어진다. 같은 좌표에 여러 점이 있을 수도 있다.
이 점들 중 서로 다른 두 점을 골라 그 거리가 가장 가깝게 만들고 싶다. 두 점 \((x_1, y_1)\), \((x_2, y_2)\) 사이의 거리는 유클리드 거리 \(\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\)로 정의된다.
정확한 정수 계산을 위해, 거리의 제곱 \((x_1 - x_2)^2 + (y_1 - y_2)^2\) 중 최솟값을 출력하여라. (제곱근을 취하지 않은 값임에 주의하라.) 두 점이 같은 좌표에 있으면 거리의 제곱은 \(0\)이다.
\(2 \le N \le 100\,000\), \(|x_i|, |y_i| \le 10^9\).
첫째 줄에 점의 개수 \(N\)이 주어진다.
이어지는 \(N\)개의 줄에 각각 두 정수 \(x_i\), \(y_i\)가 공백으로 구분되어 주어진다.
가장 가까운 두 점 사이의 거리의 제곱(정수)을 한 줄에 출력한다.
2
0 0
3 4
25
두 점뿐이므로 그 거리의 제곱 \(3^2 + 4^2 = 25\)가 답이다.
4
0 0
10 0
5 1
6 1
1
\((5,1)\)과 \((6,1)\)의 거리의 제곱이 \(1\)로 가장 작다.
riseoj 작성
출처 Original
평가 및 의견
가장 가까운 두 점
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
가장 가까운 두 점