57 10 s 128 MB
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.
Lines $1 \dots N$ : Line i contains a single integer that is the number of other fields that overlap with cow i's field.
Sample Input | Sample Output |
---|---|
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 |
NOTE: the test data will avoid pathological situations like tangents where the circles just barely touch.