Покрытие
Покрытие
Сотовый провайдер установил n башен для поддержки своей сети. Каждая башня обеспечивает покрытие в радиусе 1 км, никакие две башни не находятся на расстоянии ближе чем 1 км друг от друга. Таким образом, зоной охвата этой сети является совокупность всех точек, расположенных не далее чем 1 км от по меньшей мере одной из башен. Поставщик хочет подключить к сети максимально возможную часть региона в том смысле, что пользователь в любой точке подключенного региона может перемещаться в любую другую точку внутри подключенного региона без необходимости выхода из региона. Нынешняя установка башен может и не образовывать единую связанную область, но у провайдера есть ресурсы для строительства еще одной башни в любом месте, в том числе в пределах 1 км от любой из существующих башен.
Учитывая, что провайдер может построить еще одну башню, каково максимальное количество башен (в том числе и только что построенная), которые могут быть включены в один связный регион покрытия?
Вхідні дані
Первая строка содержит количество имеющихся башен n (1 ≤ n ≤ 5000). Каждая из следующих n строк содержит 2 действительных числа x[i]
, y[i]
(0 ≤ x[i]
, y[i]
≤ 10^5
) - координаты i-ой башни в км. Гарантируется, что оптимальное количество башен не изменится, если даже радиус покрытия всех башен будет увеличен или уменьшен на один миллиметр.
Вихідні дані
Выведите максимальное количество башен, которое может находиться в пределах одного подключенного региона сети после установки одной дополнительной башни.
Приклад
5 1.0 1.0 3.1 1.0 1.0 3.1 3.1 3.1 4.2 3.1
6
5 1.0 1.0 3.1 1.0 1.0 3.1 3.1 3.1 10.0 10.0
5