CF50D.Bombing

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The commanding officers decided to drop a nuclear bomb on the enemy's forces. You are ordered to determine the power of the warhead that needs to be used.

The enemy has NN strategically important objects. Their positions are known due to the intelligence service. The aim of the strike is to deactivate at least KK important objects of the enemy. The bombing impact point is already determined and has coordinates of [X0; Y0][X_{0};\ Y_{0}] .

The nuclear warhead is marked by the estimated impact radius R>=0R>=0 . All the buildings that are located closer than RR to the bombing epicentre will be destroyed. All the buildings that are located further than RR from the epicentre, can also be deactivated with some degree of probability. Let's assume that DD is the distance between a building and the epicentre. This building's deactivation probability P(D,R)P(D,R) is calculated according to the following formula:

We should regard as eae^{a} , where e2.7182818284590452353602874713527e≈2.7182818284590452353602874713527 If the estimated impact radius of the warhead is equal to zero, then all the buildings located in the impact point will be completely demolished and all the rest of important objects will not be damaged.

The commanding officers want the probability of failing the task to be no more than εε . Nuclear warheads are too expensive a luxury, that's why you have to minimise the estimated impact radius of the warhead.

输入格式

The first line contains an integer NN which represents the number of the enemy's objects ( 1<=N<=1001<=N<=100 ). The second line contains two integers: KK is the required number of deactivated objects, and εε is the maximally permitted probability of not completing the task, given in per mils ( 1<=K<=N1<=K<=N , 1<=ε<=9991<=ε<=999 ). The third line contains X0X_{0} and Y0Y_{0} which are the coordinates of the strike impact point. The next NN lines contain two numbers XiX_{i} and YiY_{i} each which are the coordinates of every strategically important object. All the coordinates are integer, their absolute values do not exceed 10001000 .

Let us remind you that there are a thousand per mils in unity (number one).

There can be several objects in one point.

输出格式

Print the sought estimated impact radius of the warhead. The absolute or relative measure of the inaccuracy of your answer should not exceed 10610^{-6} .

输入输出样例

  • 输入#1

    1
    1 500
    5 5
    1 2
    

    输出#1

    3.84257761518762740
    
  • 输入#2

    5
    3 100
    0 0
    3 4
    60 70
    100 100
    10 10
    5 12
    

    输出#2

    13.45126176453737600
    
首页