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

Круг и точки

Круг и точки

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Вам задано N точек на плоскости и круг единичного радиуса. Какое максимальное количество точек может быть одновременно в круге? Точка считается принадлежащей кругу, если она находится внутри круга или на его границе (на окружности).

Входные данные Вход состоит из ряда наборов данных. На окончание входных данных указывает строка, содержащая единственное число 0. Каждый набор данных начинается со строки, содержащей целое число N, которое указывает число точек в наборе данных. Далее следует N строк, описывающих координаты точек. Каждая из N строк содержит два десятичных числа X и Y, описывающих Х и Y-координаты точки, соответственно. Координаты заданы с точностью до пяти значащих цифр после десятичной точки. Известно, что 1 <= N <= 300, 0.0 <= X <= 10.0, и 0.0 <= Y <= 10.0. Никакие две точки не расположены ближе, чем на 0.0001. Никакие две точки в наборах данных не находятся приблизительно на расстоянии 2.0. Более точно – известно, что для любых двух точек в наборе данных, расстояние d между ними никогда не удовлетворяет неравенство 1.9999 <= d <= 2.0001. Наконец, никакие три точки в наборе данных не расположены одновременно очень близко к одной окружности единичного радиуса. Более того, если P_1, P_2 и P_3 - три разных точки в наборе данных, и d_1, d_2 и d_3 - расстояния от произвольно выбранной точки координатной плоскости до них соответственно, то никогда одновременно не выполняются неравенства, что 0.9999 <= d_i <= 1.0001 (i = 1, 2, 3). Выходные данные Для каждого набора входных данных в отдельной строке вывести искомое максимальное количество точек, которые могут быть помещены в круг единичного радиуса. Пример входных данных 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
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