Покриття#8189
Сотовий провайдер встановив веж для підтримки своєї мережі. Кожна вежа забезпечує покриття в радіусі км, причому жодні дві вежі не розташовані ближче ніж км одна від одної. Таким чином, зона покриття цієї мережі складається з усіх точок, що знаходяться не далі ніж км від принаймні однієї з веж. Постачальник прагне підключити до мережі якомога більшу частину регіону, щоб користувач у будь-якій точці підключеного регіону міг переміщатися до будь-якої іншої точки всередині цього регіону, не виходячи за його межі. Нинішня установка веж може не утворювати єдину зв'язану область, але у провайдера є ресурси для будівництва ще однієї вежі в будь-якому місці, включаючи зону в межах км від будь-якої з існуючих веж.
Зважаючи на можливість побудови ще однієї вежі, яке максимальне число веж (включаючи нову), може бути об'єднано в один зв'язний регіон покриття?
Перший рядок містить кількість наявних веж (1 \leq n \leq 5000). Кожен з наступних рядків містить дійсних числа x_i, y_i (0 \leq x_i, y_i \leq 10^5) - координати -ої вежі в км. Гарантується, що оптимальна кількість веж не зміниться, навіть якщо радіус покриття всіх веж буде збільшено або зменшено на один міліметр.
Виведіть максимальну кількість веж, які можуть бути включені в один зв'язний регіон мережі після встановлення однієї додаткової вежі.
Приклад 1
Приклад 2