Armistice Area Apportionment

题目描述

After a drawn-out mooclear arms race, Farmer John and the Mischievous Mess Makers have finally agreed to establish peace. They plan to divide the territory of Bovinia with a line passing through at least two of the $ n $ outposts scattered throughout the land. These outposts, remnants of the conflict, are located at the points $ (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n}) $ . In order to find the optimal dividing line, Farmer John and Elsie have plotted a map of Bovinia on the coordinate plane. Farmer John's farm and the Mischievous Mess Makers' base are located at the points $ P=(a,0) $ and $ Q=(-a,0) $ , respectively. Because they seek a lasting peace, Farmer John and Elsie would like to minimize the maximum difference between the distances from any point on the line to $ P $ and $ Q $ . Formally, define the difference of a line  relative to two points $ P $ and $ Q $ as the smallest real number $ d $ so that for all points $ X $ on line , $ |PX-QX|<=d $ . (It is guaranteed that $ d $ exists and is unique.) They wish to find the line  passing through two distinct outposts $ (x_{i},y_{i}) $ and $ (x_{j},y_{j}) $ such that the difference of  relative to $ P $ and $ Q $ is minimized.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ a $ ( $ 2<=n<=100000 $ , $ 1<=a<=10000 $ ) — the number of outposts and the coordinates of the farm and the base, respectively. The following $ n $ lines describe the locations of the outposts as pairs of integers $ (x_{i},y_{i}) $ ( $ |x_{i}|,|y_{i}|<=10000 $ ). These points are distinct from each other as well as from $ P $ and $ Q $ .

输出格式

Print a single real number—the difference of the optimal dividing line. Your answer will be considered correct if its absolute or relative error does not exceed $ 10^{-6} $ . Namely: let's assume that your answer is $ a $ , and the answer of the jury is $ b $ . The checker program will consider your answer correct, if .

输入输出样例

输入样例 #1

2 5
1 0
2 1

输出样例 #1

7.2111025509

输入样例 #2

3 6
0 1
2 5
0 -3

输出样例 #2

0.0000000000

说明

In the first sample case, the only possible line  is $ y=x-1 $ . It can be shown that the point $ X $ which maximizes $ |PX-QX| $ is $ (13,12) $ , with , which is . In the second sample case, if we pick the points $ (0,1) $ and $ (0,-3) $ , we get  as $ x=0 $ . Because $ PX=QX $ on this line, the minimum possible difference is $ 0 $ .

题意翻译

给定平面上 $n$ 个点和 $a$。设 $P(a,0),Q(-a,0)$。要求找出一条直线 $l$ 过至少两个给定点，最小化 $\max\{ |PX-QX|\},X\in l$。 $n\le10^5,a\le 10^4$。