| Codeforces Beta Round 47 |
|---|
| Закончено |
Командование решило нанести ядерный удар по силам противника. Вам приказали определить мощность боеголовки, которую нужно использовать.
У противника есть 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 500
5 5
1 2
3.84257761518762740
5
3 100
0 0
3 4
60 70
100 100
10 10
5 12
13.45126176453737600
