문제1811--Crop Circles

1811: Crop Circles

실행시간 제한: 10 Sec  메모리사용 제한: 128 MB
제출: 86  통과: 72
[제출] [채점기록] [묻고답하기]

문제 설명

Bessie and her fellow herd-mates have become extremely territorial. The $N$ $(1 \leq N \leq 400)$ cows conveniently numbered $1 \dots N$ have all staked out a grazing spot in the pasture. Each cow $i$ has a spot on an integer grid $(0 \leq X_i \leq 10,000; 0 \leq Y_i \leq 10,000)$ and an integer radius $R_i$ that indicates the circle she is staking out $(1 \leq R_i \leq 500)$.

The cows are a bit greedy and sometimes stake out territory of their herd-mates. For each cow, calculate the number of other cows whose territory overlaps her territory.

By way of example, consider these six cows with indicated locations and radii (don't confuse radius with diameter!):

By visual inspection, we can see and count the overlaps, as shown.

입력 설명

  • Line $1$: A single integer: $N$
  • Lines $2 \dots N+1$: Three space-separated integers: $X_i$, $Y_i$, and $R_i$

출력 설명

  • Lines $1 \dots N$ : Line i contains a single integer that is the number of other fields that overlap with cow i's field.

입력 예시 Copy

6
7 7 7
16 14 7
11 13 2
10 17 3
29 8 5
15 7 4

출력 예시 Copy

3
4
3
2
0
2

도움

NOTE: the test data will avoid pathological situations like tangents where the circles just barely touch.

출처/분류