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

Круг та точки

Круг та точки

\includegraphics{https://static.e-olymp.com/content/d8/d89ac64ee646745e0900ce85bab77af31f3bfb5d.jpg} Вам задано \textbf{N} точок на площині та круг одиничного радіуса. Яка найбільша кількість точок може знаходитись у крузі? Вважається, що точка належить кругу, якщо вона знаходиться у крузі, або на його границі (на колі). \textbf{Вхідні дані} Вхідні дані містять ряд наборів даних. Про закінчення вхідних даних свідчить рядок, що містить єдине число \textbf{0}. Кожен набір даних починається з рядка, який містить ціле число \textbf{N} кількість точок у наборі даних. Далі йде \textbf{N} рядків, які задають координати точок. Кожен з \textbf{N} рядків містить два десяткових числа \textbf{X} та \textbf{Y}, що задають \textbf{Х} та \textbf{Y}-координати точки, відповідно. Координати задано з точністю до п'яти значущих цифр після десяткової крапки. Відомо, що \textbf{1} <= \textbf{N} <= \textbf{300}, \textbf{0.0} <= \textbf{X} <= \textbf{10.0}, і \textbf{0.0} <= \textbf{Y} <= \textbf{10.0}. Ніякі дві точки не розміщені ближче, ніж на \textbf{0.0001}. Ніякі дві точки у наборах даних не знаходяться приблизно на відстані \textbf{2.0}. Більше того, відомо, що для довільних двох точок у наборі даних, відстань \textbf{d} між ними ніколи не задовольняє нерівність \textbf{1.9999} <= \textbf{d} <= \textbf{2.0001}. Нарешті, ніякі три точки у наборі даних не розміщені одночасно дуже близько до єдиного кругу одиничного радіуса. Більше того, якщо \textbf{P_1}, \textbf{P_2} і \textbf{P_3} - три різні точки у наборі даних, і \textbf{d_1}, \textbf{d_2} та \textbf{d_3} - відстані від довільно вибраної точки в крузі до кожної з них відповідно, то тоді ніколи одночасно не виконуються нерівності: \textbf{0.9999} <= \textbf{d_i} <= \textbf{1.0001} (i = 1, 2, 3). \textbf{Вихідні дані} Для кожного набору вхідних даних в окремому рядку вивести шукану максимальну кількість точок, які можуть бути розміщені в крузі одиничного радіуса. \textbf{Приклад вхідних даних} 3 6.47634 7.69628 5.16828 4.79915 6.69533 6.20378 6 7.15296 4.08328 6.50827 2.69466 5.91219 3.86661 5.29853 4.16097 6.10838 3.46039 6.34060 2.41599 8 7.90650 4.01746 4.10998 4.18354 4.67289 4.01887 6.33885 4.28388 4.98106 3.82728 5.12379 5.16473 7.84664 4.67693 4.02776 3.87990 20 6.65128 5.47490 6.42743 6.26189 6.35864 4.61611 6.59020 4.54228 4.43967 5.70059 4.38226 5.70536 5.50755 6.18163 7.41971 6.13668 6.71936 3.04496 5.61832 4.23857 5.99424 4.29328 5.60961 4.32998 6.82242 5.79683 5.44693 3.82724 6.70906 3.65736 7.89087 5.68000 6.23300 4.59530 5.92401 4.92329 6.24168 3.81389 6.22671 3.62210 0
Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3
6.47634 7.69628
5.16828 4.79915
6.69533 6.20378
6
7.15296 4.08328
6.50827 2.69466
5.91219 3.86661
5.29853 4.16097
6.10838 3.46039
6.34060 2.41599
8
7.90650 4.01746
4.10998 4.18354
4.67289 4.01887
6.33885 4.28388
4.98106 3.82728
5.12379 5.16473
7.84664 4.67693
4.02776 3.87990
20
6.65128 5.47490
6.42743 6.26189
6.35864 4.61611
6.59020 4.54228
4.43967 5.70059
4.38226 5.70536
5.50755 6.18163
7.41971 6.13668
6.71936 3.04496
5.61832 4.23857
5.99424 4.29328
5.60961 4.32998
6.82242 5.79683
5.44693 3.82724
6.70906 3.65736
7.89087 5.68000
6.23300 4.59530
5.92401 4.92329
6.24168 3.81389
6.22671 3.62210
8
7.90650 4.01746
4.10998 4.18354
4.67289 4.01887
6.33885 4.28388
4.98106 3.82728
5.12379 5.16473
7.84664 4.67693
4.02776 3.87990
0
Вихідні дані #1
2
5
5
11
5