Земли Антарктиды

prb1685 На карте Антарктики точками изображено N полярных станций, каждая из которых имеет натуральные координаты в прямоугольной сетке. Переход между двумя станциями возможен, если расстояние между ними по прямой меньше двух единичных отрезков карты. Станции, между которыми существует прямое или транзитное соединение, объединяются в земли, причём каждая станция принадлежит только одной земле.

Нужно определить K – количество арктических земель.

Технические условия

Входные данные

В первой строке файла записано одно число N – количество станций, а в последующих N строках по два числа – координаты каждой из них. Все числовые значения натуральные и не превышают 100.

Выходные данные

Единственное число – количество земель.

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 9% 104/114
Автор: Матвийчук С.В.
Классификация: Теория графов, Жадный алгоритм

Пример

Пример входных данных

Пример выходных данных

← Мобильный тариф "Копейка"

Список задач