설계도의 비밀
골드 IV의견: 0
고대 제국의 발굴 현장에서 설계도 한 장이 발견되었다. 설계도에는 \(N\)개의 유적 좌표 \((x_i, y_i)\)가 표시되어 있다. 고고학자들은 설계도에서 가장 가까운 두 유적 사이의 거리를 알아내고 싶다.
두 유적 \((x_a, y_a)\), \((x_b, y_b)\) 사이의 거리의 제곱은 \((x_a - x_b)^2 + (y_a - y_b)^2\)이다. 가장 가까운 두 유적 사이의 거리의 제곱을 출력하여라.
- \(2 \le N \le 150\,000\)
- \(-10^9 \le x_i, y_i \le 10^9\)
- 좌표는 정수이다.
첫째 줄에 유적의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각 유적의 좌표 \(x_i\), \(y_i\)가 공백으로 구분되어 주어진다. 모든 좌표는 정수이며, 같은 좌표에 두 개 이상의 유적이 있을 수 있다 (이 경우 거리의 제곱은 \(0\)이다).
가장 가까운 두 유적 사이의 거리의 제곱을 출력한다.
4
0 0
3 4
1 1
5 2
2
두 점 \((0,0)\)과 \((1,1)\) 사이의 거리의 제곱은 \(1^2+1^2=2\)이다. 다른 쌍은 모두 이보다 크므로 답은 \(2\)이다.
4
0 0
6 0
3 4
3 -4
25
가장 가까운 두 쌍은 여럿이며 거리의 제곱이 모두 \(25\)이다. 예를 들어 \((0,0)\)과 \((3,4)\) 사이의 거리의 제곱은 \(9+16=25\)이다.
riseoj 작성
출처 Original
평가 및 의견
설계도의 비밀
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
설계도의 비밀