City Major

Statement:

Toby has got a lot of popularity since he defeated Humbertov Moralov in the Primoshkas war. He was elected major of Tobyland and now he is running for the elections again. Unfortunately for him the Rottweiler associations controls all the communication media. This associations doesn't like Toby because they believe only big and strong dogs should rule the city, and Toby is only a small and cute dog.

Thus Toby plans to create a new TV station that support his cause. Toby is short of budget to buy the antennas but he knows he doesn't need to cover all the population to win the elections. Toby's city is represented as a non self-intersecting polygon, given the location of the TV station your task is to find the minimum radius of coverage around the TV station such that at least p percent of the population (p% of the polygon area) is inside the radius of coverage. Assume that the TV station is located in the origin (0, 0), the TV station could be inside or outside of the city polygon.

Input:

The input consists fo several test cases. Each test case begins with a line with two integers 3 ≤ N ≤ 100 and 1 ≤ P ≤ 100 representing the number of vertices and the percentage of coverage required. Then follows N lines with two integers xi and yi (-100000 ≤ xi, yi ≤ 100000) indicating the position of vertex number i. The end of the input is given by the end of file.

Output:

For each test case, print a single line containing the minimum radius of coverage as explained above. Print your answer with 2 decimal digits.

Example input:
4 100
1 1
1 -1
-1 -1
-1 1
3 39
0 0
0 2
2 0
Example output:
1.41
1.00
Time and memory limit:

  • 1s
  • 64MB

Problem source: Caribbean Online Judge