Круг та точки#299

Круг та точки

2 секунди

64 мегабайти

Середня

Вам задано $N$ точок на площині $x y$ та коло радіуса $1$ .

Знайдіть максимальну кількість точок, які можуть одночасно знаходитись всередині або на межі кола радіуса $1$ . Точка вважається всередині кола, якщо вона знаходиться всередині або точно на межі кола.

Вхідні дані

Вхід складається з кількох наборів даних. Кінець вхідних даних позначається рядком, що містить єдиний $0$ .

Кожен набір даних починається з рядка, який містить одне ціле число $N$ ( $1 \leq N \leq 300$ 1 \le N \le 300) — кількість точок.

Далі слідують $N$ рядків, кожен з яких містить два десяткових числа $X$ та $Y$ ( $0.0 \leq X, Y \leq 10.0$ 0.0 \le X, Y \le 10.0) — координати точки. Кожна координата задана з $5$ знаками після десяткової крапки.

Жодна пара точок не знаходиться ближче, ніж $0.0001$ одна до одної. Жодна пара точок у наборі не знаходиться на відстані приблизно $2.0$ одна від одної, тобто, відстань $d$ між будь-якою парою точок ніколи не задовольняє $1.9999 \leq d \leq 2.0001$ 1.9999 \le d \le 2.0001.

Крім того, жодні три точки в наборі не є одночасно дуже близькими до того, щоб лежати на одному колі радіуса $1$ . А саме, для будь-яких трьох різних точок $P_{1}$ P_1, $P_{2}$ P_2, $P_{3}$ P_3 у наборі і для будь-якої довільної точки на площині, нехай $d_{1}$ d_1, $d_{2}$ d_2, $d_{3}$ d_3 — відстані від цієї точки до $P_{1}$ P_1, $P_{2}$ P_2, $P_{3}$ P_3 відповідно. Тоді ніколи не виконується одночасно $0.9999 \leq d_{i} \leq 1.0001$ 0.9999 \le d_i \le 1.0001 для $i = 1, 2, 3$ i = 1,2,3.

Вихідні дані

Для кожного набору даних виведіть максимальну кількість точок, які можуть одночасно знаходитися всередині або на колі радіуса $1$ , одним числом у кожному рядку.

Приклади

Приклад 1