Авария и Go(relians)
Горелиане — это воинственная раса, которая путешествует по вселенной, завоевывая новые миры ради развлечения. Обычно их космические битвы проходят довольно односторонне, но иногда даже горелиане терпят поражение. В одном из таких проигранных сражений их космический корабль был настолько поврежден, что им пришлось эвакуироваться на планету ниже. Из-за хаоса (и потому что спасательные капсулы не очень точны) горелиане оказались разбросаны по большой площади планеты (но достаточно малой, чтобы мы могли моделировать поверхность планеты как плоскую, а не сферическую). Ваша задача — отслеживать их усилия по воссоединению. К счастью, каждая спасательная капсула оснащена локатором, который сообщает горелианину его текущие координаты на планете, и радиопередатчиком, который можно использовать для связи с другими горелианами. К сожалению, дальность действия радиопередатчиков ограничена количеством энергии.
Когда горелианин приземляется на чужой планете, первое, что он делает, — проверяет радио, чтобы узнать, может ли он связаться с другими горелианами. Если может, то договаривается о месте встречи с ними, и они сходятся в этой точке. Собравшись вместе, они могут объединить источники питания своих радиопередатчиков, что увеличивает дальность радиосвязи. Затем они повторяют процесс — смотрят, кого могут достичь, договариваются о месте встречи, объединяют свои радиопередатчики — до тех пор, пока не смогут больше связаться с другими горелианами.
Технология горелиан позволяет двустороннюю связь, если хотя бы один из них имеет радиопередатчик с достаточной дальностью, чтобы покрыть расстояние между ними. Например, предположим, что у Алисы радиус действия радиопередатчика 40 км, а у Боба — 30 км, но они находятся на расстоянии 45 км друг от друга (Рисунок 1). Поскольку ни у кого из них нет радиопередатчика с достаточной дальностью, чтобы достичь другого, они не могут общаться. Однако, если они находятся на расстоянии всего 35 км друг от друга (Рисунок 2), радиус действия радиопередатчика Боба все еще недостаточен, чтобы достичь Алисы, но это не имеет значения — они все равно могут общаться, потому что радиус действия радиопередатчика Алисы достаточен, чтобы достичь Боба.
Если горелианин успешно связывается с другими горелианами, они встречаются в точке, которая является средним значением всех их местоположений. В случае Алисы и Боба это будет просто середина между A и B (Рисунок 3). Заметьте, что горелиане выключают свои радиопередатчики во время путешествия; они не будут пытаться связаться с кем-либо еще, пока все не соберутся в месте встречи. Как только горелиане встречаются, они объединяют свои радиопередатчики, чтобы создать новый радиопередатчик с большей дальностью. В частности, площадь, покрываемая новым радиопередатчиком, равна сумме площадей, покрываемых старыми радиопередатчиками. В нашем примере у Алисы был радиус действия 40 км, так что ее радиопередатчик покрывал площадь 1600π км². Радиопередатчик Боба покрывал площадь 900π км². Таким образом, когда они объединяют свои радиопередатчики, они могут покрыть 2500π км² — это означает, что у них радиус действия 50 км. На этом этапе они снова попытаются связаться с другими горелианами.
Этот процесс продолжается до тех пор, пока не удастся связаться с другими горелианами. Например, предположим, что следующие горелиане все приземлились и у всех радиус действия радиопередатчика 30 км: Алиса (100, 100), Боб (130, 80), Кэти (80, 60) и Дэйв (120, 150). На этом этапе ни один из горелиан не может связаться с кем-либо еще (Рисунок 5). Теперь Эдди приземляется в позиции (90, 80) (Рисунок 6). Эдди может связаться с Алисой и Кэти, поэтому они договариваются встретиться в точке (90, 80), которая является средним значением их местоположений. Объединение их радиопередатчиков дает им радиус действия √2700 ≈ 51.96 км (Рисунок 7).
Теперь они снова проверяют с их новым улучшенным радиусом действия и обнаруживают, что могут достичь Боба. Поэтому они встречаются с Бобом в точке (110, 80) и объединяют свои радиопередатчики, чтобы получить новый радиопередатчик с радиусом действия 60 км (Рисунок 8). К сожалению, этого недостаточно, чтобы достичь Дэйва, поэтому Дэйв остается изолированным.
Входные данные
Входные данные состоят из одного или нескольких наборов данных. Каждый набор данных начинается с целого числа ( N ), представляющего количество горелиан в этом наборе данных (1 ≤ ( N ) ≤ 100). Значение ( N = 0 ) указывает на конец ввода.
Далее следуют ( N ) строк, каждая из которых содержит три целых числа ( X ), ( Y ) и ( R ), представляющих координаты ( x ) и ( y ), где приземляется горелианин, и радиус действия радиопередатчика (0 ≤ ( X ), ( Y ) ≤ 1000, и 1 ≤ ( R ) ≤ 1000). Обратите внимание, что только начальные координаты и радиус действия горелиан будут целыми; после объединения с другими горелианами они могут больше не быть целыми. Вы должны использовать арифметику двойной точности для всех вычислений.
Горелиане приземляются в порядке, в котором они появляются в входном файле. Когда горелианин приземляется, он объединяется с любыми горелианами, с которыми может связаться, и процесс продолжается до тех пор, пока не удастся сделать больше объединений. Следующий горелианин не приземляется, пока все предыдущие объединения не будут завершены.
Выходные данные
Вывод должен содержать одну строку на каждый набор данных, сообщающую количество независимых групп горелиан, оставшихся в конце процесса.