가장 가까운 거점
다이아몬드 I의견: 0
평면 위에 \(N\)개의 거점이 있다. \(i\)번째 거점의 좌표는 \((x_i, y_i)\)이다.
이후 \(Q\)개의 질의 지점이 주어진다. 각 질의 지점 \((qx, qy)\)에 대해, 그 지점에서 유클리드 거리가 가장 가까운 거점의 번호와, 그 거점까지의 거리의 제곱을 출력해야 한다.
가장 가까운 거점이 여러 개라면(거리가 같다면) 그중 번호가 가장 작은 거점을 답한다.
거리의 제곱은 \((qx - x_i)^2 + (qy - y_i)^2\)로 정의되며, 모든 좌표가 정수이므로 이 값은 항상 정수이다.
\(1 \le N, Q \le 100{,}000\)
\(-10^9 \le x_i, y_i, qx, qy \le 10^9\)
서로 다른 두 거점이 같은 좌표에 있을 수 있다.
첫 줄에 거점 수 \(N\)과 질의 수 \(Q\)가 주어진다.
다음 \(N\)개의 줄에 각 거점의 좌표 \(x_i\), \(y_i\)가 주어진다.
이어서 \(Q\)개의 줄에 각 질의 지점의 좌표 \(qx\), \(qy\)가 주어진다.
각 질의마다 한 줄에 두 정수를 출력한다: 가장 가까운 거점의 번호(1번부터 시작)와 그 거점까지의 거리의 제곱.
3 3
0 0
10 0
5 8
1 1
9 1
5 5
1 2
2 2
3 9거점은 (0,0),(10,0),(5,8). 질의 (1,1)은 1번 거점에 가장 가까워 거리제곱 2. 질의 (9,1)은 2번 거점에 가까워 거리제곱 (9-10)^2+1=2. 질의 (5,5)는 3번 거점 (5,8)까지 거리제곱 9로 가장 가깝다.
2 2
0 0
4 0
2 0
2 3
1 4
1 13두 거점 (0,0),(4,0)에서 질의 (2,0)은 양쪽 모두 거리제곱 4로 같으므로 번호가 작은 1번을 답한다. 질의 (2,3)도 양쪽 거리제곱이 13으로 같아 1번을 답한다.
riseoj 작성
출처 Original
평가 및 의견
가장 가까운 거점
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
가장 가까운 거점