겹치는 방목 구역

면접 대비

시간 제한1초메모리 제한128 MB

요약
N개의 원이 주어질 때, 각 원이 다른 원과 겹치는 개수를 두 중심 거리와 반지름 합의 비교로 세어 출력한다.
난이도

쉬움10점 중 3점

유형
기하, 완전 탐색, 구현, 수학
정답자
아직 제출이 없습니다

문제

베시와 동료 소들이 영역 다툼을 벌이기 시작했습니다. 11번부터 NN번까지 번호가 매겨진 NN마리의 소가 각자 목초지에 자기 방목 구역을 차지했습니다. 소 ii는 정수 좌표 (Xi,Yi)(X_i, Y_i)를 중심으로 하고 정수 반지름 RiR_i를 갖는 원형 구역을 차지합니다. (1≤N≤4001 \le N \le 400, 0≤Xi≤100000 \le X_i \le 10000, 0≤Yi≤100000 \le Y_i \le 10000, 1≤Ri≤5001 \le R_i \le 500)

소들은 조금 욕심이 많아서 종종 서로의 구역을 침범합니다. 각 소에 대해, 그 소의 구역과 겹치는 다른 소들의 구역이 몇 개인지 세어야 합니다.

두 구역은 두 원의 중심 사이 거리가 두 반지름의 합보다 엄격히 작을 때 겹치는 것으로 봅니다. 즉, 소 ii와 소 jj의 구역이 겹치는 조건은 다음과 같습니다.

(Xi−Xj)2+(Yi−Yj)2<(Ri+Rj)2(X_i - X_j)^2 + (Y_i - Y_j)^2 < (R_i + R_j)^2

(한 구역이 다른 구역을 완전히 포함하는 경우도 겹치는 것으로 봅니다.)

예를 들어, 아래 그림처럼 위치와 반지름이 주어진 여섯 마리의 소를 생각해 봅시다 (반지름과 지름을 혼동하지 마세요!).

그림을 눈으로 살펴보면 겹침을 세어 볼 수 있습니다.

참고: 테스트 데이터에는 두 원이 정확히 맞닿는(접하는) 경계 상황은 포함되지 않습니다.

입력

  • 첫째 줄: 정수 NN
  • 둘째 줄부터 N+1N+1째 줄까지: 공백으로 구분된 세 정수 XiX_i, YiY_i, RiR_i

출력

  • NN개의 줄을 출력합니다. ii번째 줄에는 소 ii의 구역과 겹치는 다른 소들의 구역 개수를 정수 하나로 출력합니다.

예제1

  1. 예제 1

    입력
    6
7 7 7
16 14 7
11 13 2
10 17 3
29 8 5
15 7 4
    예상 출력
    3
4
3
2
0
2