ICPC SWERC 2017 K - Blowing Candles

View as PDF

Submit solution


Points: 15
Time limit: 4.0s
Memory limit: 1G

Problem type

As Jacques-Édouard really likes birthday cakes, he celebrates his birthday every hour, instead of every year. His friends ordered him a round cake from a famous pastry shop, and placed candles on its top surface. The number of candles equals the age of Jacques-Édouard in hours. As a result, there is a huge amount of candles burning on the top of the cake. Jacques-Édouard wants to blow all the candles out in one single breath.

You can think of the flames of the candles as being points in the same plane, all within a disk of radius R (in nanometers) centered at the origin. On that same plane, the air blown by Jacques-Édouard follows a trajectory that can be described by a straight strip of width W, which comprises the area between two parallel lines at distance W, the lines themselves being included in that area. What is the minimum width W such that Jacques-Édouard can blow all the candles out if he chooses the best orientation to blow?

Input Specification

The first line consists of the integers N and R, separated with a space, where N is Jacques-Édouard's age in hours. Then N lines follow, each of them consisting of the two integer coordinates x_i and y_i of the i^{th} candle in nanometers, separated with a space.

Constraints

  • 3 \le N \le 2 \cdot 10^5;
  • 10 \le R \le 2 \cdot 10^8;
  • for 1 \le i \le N, x_i^2 + y_i^2 \le R^2;
  • all points have distinct coordinates.

Output Specification

Print the value W as a floating point number. Your answer will be considered correct if it has an absolute or relative error of at most 10^{-5}.

Sample Input

3 10
0 0
10 0
0 10

Sample Output

7.0710678118654755

Comments

There are no comments at the moment.