Круги с посевами
Круги с посевами
Бесси и ее друзья из стада стали слишком территориальными. n коров, пронумерованные 1..n, собрались на пастбище. Каждая i-ая корова задается точкой в целочисленной системе координат (xi
, yi
) и целочисленным радиусом ri
, характеризующим круг ее занимаемой территории.
Иногда коровы становятся жадными и начинают ходить на территории своих соседей. Вычислите для каждой коровы количество соседей, чьи территории пересекаются с ее.
Рассмотрим пример с шестью коровами и указанными их местами расположения с радиусами территориальных кругов (не путайте радиус с диаметром!):
Как показано на рисунке, для каждого круга количество его пересечений с другими кругами подсчитать не сложно.
Замечание: во входных данных отсутствуют случаи касания кругов.
Входные данные
Первая строка содержит целое число n (1 ≤ n ≤ 400). Каждая из следующих n строк содержит три целых числа xi
, yi
(0 ≤ xi
≤ 10000, 0 ≤ yi
≤ 10000) и ri
(1 ≤ ri
≤ 500).
Выходные данные
Вывести n строк. i-ая строка должна содержать количество кругов, с которыми пересекается поле i-ой коровы.
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