Crop Circles

Interview

Time limit1sMemory limit128 MB

Summary
Given N circles, count for each circle how many of the other circles it overlaps, using the strict distance-versus-sum-of-radii test.
Level

Easy3 of 10

Topics
Geometry, Brute force, Implementation, Math
Solved
No attempts yet

Problem

Bessie and her herd-mates have become extremely territorial. The NN cows, numbered 11 through NN, have each staked out a grazing spot in the pasture. Cow ii claims a circular territory centered at integer coordinates (Xi,Yi)(X_i, Y_i) with an integer radius 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).

The cows are a bit greedy and sometimes stake out territory that intrudes on their herd-mates. For each cow, count how many of the other cows' territories overlap hers.

Two territories overlap when the distance between their centers is strictly less than the sum of their radii; that is, cow ii and cow jj overlap exactly when

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

(One territory completely containing another also counts as overlapping.)

As an example, consider these six cows with the indicated locations and radii (don't confuse radius with diameter!):

By visual inspection you can see and count the overlaps.

Note: the test data avoids pathological situations such as tangents, where two circles just barely touch.

Input

  • Line 1: a single integer NN.
  • Lines 2 to N+1N+1: three space-separated integers XiX_i, YiY_i, and RiR_i.

Output

  • Print NN lines. Line ii contains a single integer: the number of other cows' territories that overlap cow ii's territory.

Examples1

  1. Example 1

    Input
    6
7 7 7
16 14 7
11 13 2
10 17 3
29 8 5
15 7 4
    Expected output
    3
4
3
2
0
2