Олимпиадный тренинг

Задача . D. Бомбардировка


Задача

Темы: Бинарный поиск дп Теория вероятностей *2100

Командование решило нанести ядерный удар по силам противника. Вам приказали определить мощность боеголовки, которую нужно использовать.

У противника есть N стратегически важных объектов. Их позиции известны благодаря проведённой разведке. Цель удара — вывести из строя как минимум K важных объектов противника. Место нанесения удара уже определено и имеет координаты [X0; Y0].

Ядерная боеголовка маркируется расчётным радиусом поражения R ≥ 0. Все сооружения, находящиеся на расстоянии ближе R от эпицентра взрыва, будут разрушены. Все сооружения, находящиеся на расстоянии больше R от эпицентра, также могут быть выведены из строя с некоторой вероятностью. Пусть D — расстояние от эпицентра до сооружения. Вероятность выведения этого сооружения из строя P(D, R) вычисляется по следующей формуле:

Под следует понимать ea, где e ≈ 2.7182818284590452353602874713527

Если же расчётный радиус поражения боеголовки равен нулю, то все сооружения, находящиеся в точке нанесения удара, будут полностью разрушены, а все остальные важные объекты повреждены не будут.

Командование хочет, чтобы вероятность провалить задание была не более ε. Ядерные боеголовки — дорогое удовольствие, поэтому от вас требуется минимизировать расчётный радиус поражения боеголовки.

Входные данные

В первой строке записано целое число N — количество объектов противника (1 ≤ N ≤ 100). Во второй строке записано два целых числа: K — целевое количество выведенных из строя объектов, и ε — максимально допустимая вероятность не выполнить задачу, заданная в промилле (1 ≤ K ≤ N, 1 ≤ ε ≤ 999). В третьей строке записаны X0 и Y0 – координаты точки нанесения удара. Остальные N строк содержат по два числа Xi и Yi — координаты каждого стратегически важного объекта. Все координаты целые, по модулю не превосходят 1000.

Напоминаем, что в единице тысяча промилле.

В одной точке может находиться несколько объектов.

Выходные данные

Выведите искомый расчётный радиус поражения боеголовки. Абсолютная или относительная погрешность вашего ответа не должна превышать 10 - 6.


Примеры
№Входные данныеВыходные данные
1 1
1 500
5 5
1 2 
3.84257761518762740
2 5
3 100
0 0
3 4
60 70
100 100
10 10
5 12 
13.45126176453737600

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет