Armistice Area Apportionment
题意翻译
给定平面上 $n$ 个点和 $a$。设 $P(a,0),Q(-a,0)$。要求找出一条直线 $l$ 过至少两个给定点,最小化 $\max\{ |PX-QX|\},X\in l$。
$n\le10^5,a\le 10^4$。
题目描述
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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF645G/2753c32f9c54ae7cab12385d23f18081312044d2.png) relative to two points $ P $ and $ Q $ as the smallest real number $ d $ so that for all points $ X $ on line ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF645G/2753c32f9c54ae7cab12385d23f18081312044d2.png), $ |PX-QX|<=d $ . (It is guaranteed that $ d $ exists and is unique.) They wish to find the line ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF645G/2753c32f9c54ae7cab12385d23f18081312044d2.png) passing through two distinct outposts $ (x_{i},y_{i}) $ and $ (x_{j},y_{j}) $ such that the difference of ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF645G/2753c32f9c54ae7cab12385d23f18081312044d2.png) 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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF645G/259203790d90e969d73ec841bd0673c1e8e7d69a.png).
输入输出样例
输入样例 #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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF645G/2753c32f9c54ae7cab12385d23f18081312044d2.png) is $ y=x-1 $ . It can be shown that the point $ X $ which maximizes $ |PX-QX| $ is $ (13,12) $ , with ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF645G/ab84998f9f7801770ba08bb5d2671f87c4a0bd74.png), which is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF645G/f4247f73c0f35a61df887577574012617090c30d.png).
In the second sample case, if we pick the points $ (0,1) $ and $ (0,-3) $ , we get ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF645G/2753c32f9c54ae7cab12385d23f18081312044d2.png) as $ x=0 $ . Because $ PX=QX $ on this line, the minimum possible difference is $ 0 $ .