eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Покрытие

Покрытие

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Сотовый провайдер установил n башен для поддержки своей сети. Каждая башня обеспечивает покрытие в радиусе 1 км, никакие две башни не находятся на расстоянии ближе чем 1 км друг от друга. Таким образом, зоной охвата этой сети является совокупность всех точек, расположенных не далее чем 1 км от по меньшей мере одной из башен. Поставщик хочет подключить к сети максимально возможную часть региона в том смысле, что пользователь в любой точке подключенного региона может перемещаться в любую другую точку внутри подключенного региона без необходимости выхода из региона. Нынешняя установка башен может и не образовывать единую связанную область, но у провайдера есть ресурсы для строительства еще одной башни в любом месте, в том числе в пределах 1 км от любой из существующих башен.

Учитывая, что провайдер может построить еще одну башню, каково максимальное количество башен (в том числе и только что построенная), которые могут быть включены в один связный регион покрытия?

Вхідні дані

Первая строка содержит количество имеющихся башен n (1n5000). Каждая из следующих n строк содержит 2 действительных числа x[i], y[i] (0x[i], y[i]10^5) - координаты i-ой башни в км. Гарантируется, что оптимальное количество башен не изменится, если даже радиус покрытия всех башен будет увеличен или уменьшен на один миллиметр.

Вихідні дані

Выведите максимальное количество башен, которое может находиться в пределах одного подключенного региона сети после установки одной дополнительной башни.

Приклад

Вхідні дані #1
5
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
4.2 3.1
Вихідні дані #1
6
Вхідні дані #2
5
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
10.0 10.0
Вихідні дані #2
5
Джерело 2015 ACM North America - Pacific Northwest, Дивизион 1, Задача I