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

Круг и точки

Круг и точки

Вам задано \textbf{n} точек на плоскости и круг единичного радиуса. Какое максимальное количество точек может быть одновременно в круге? Точка считается принадлежащей кругу, если она находится внутри круга или на его границе (на окружности). \includegraphics{https://static.e-olymp.com/content/96/9640a82ff232647e5389abde7fea922fee249594.jpg} \textit{\textbf{Рис 1}}. Окружность и точки \InputFile Состоит из нескольких тестов. Последняя строка содержит единственный \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} (\textbf{i} = \textbf{1}, \textbf{2}, \textbf{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 \textbf{Пример выходных данных} \begin{verbatim} 2\end{verbatim}\begin{verbatim} 5\end{verbatim}\begin{verbatim} 5\end{verbatim}\begin{verbatim} 11\end{verbatim}
Лимит времени 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
0
Выходные данные #1
2
5
5
11
Источник 2004 ACM International Collegiate Programming Contest, Japan Domestic Contest, Ehime, Япония, Июль 2, Задача D