Кольца и клей
Кольца и клей
Маленький Джон в большой беде. Играть с цветными кольцами разного размера и клеем казалось хорошей идеей. Однако кольца теперь лежат на полу, склеенные чем-то. Как ни удивительно, но на самом деле никакие кольца не приклеены к полу, а только к другим кольцам.
Вы должны помочь Маленькому Джону подобрать кольца с пола до того, как его мама вернется с работы. Поскольку клей уже высох, это кажется достаточно простой задачей. Это не тот случай. Маленький Джон - иррациональный ребенок с числами, поэтому он решил сначала взять самую большую компоненту (наибольшее количество) склеенных колец. Это количество колец в самой большой компоненте, которое Вас просят найти. Два кольца склеиваются тогда и только тогда, когда они перекрываются в какой-то точке, но никакие кольца никогда не будут перекрываться только в одной точке. Все кольца пончиковые (с дырочкой). Однако, по словам Маленького Джона, их можно считать "бесконечно тонкими".
Входные данные
Состоит из нескольких тестов. Каждый тест начинается с количества колец n (0 ≤ n < 100). После этого следуют n строк, каждая из которых содержит физические атрибуты кольца. То есть 3 действительных числа с произвольным количеством пробелов между ними, описывающие координату x и y центра и радиуса. Вход заканчивается единственной строкой с целым числом -1.
Выходные данные
Для каждого теста в отдельной строке выведите "The largest component contains X ring(s).", где X - количество колец в наибольшей компоненте.
4 0.0 0.0 1.0 -1.5 -1.5 0.5 1.5 1.5 0.5 -2.0 2.0 3.5 3 3.0 2.0 2.0 0.0 -0.5 1.0 0.0 0.0 2.0 5 -2.0 0.0 1.0 1.0 -1.0 1.0 0.0 1.0 0.5 2.0 0.0 1.0 -1.0 1.0 1.0 -1
The largest component contains 4 rings. The largest component contains 2 rings. The largest component contains 3 rings.