CROC 2016 - Elimination Round
G
Armistice Area Apportionment
Codeforces
3200
原题
← F→
翻译中…

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 image relative to two points $*P*$ and $*Q*$ as the smallest real number $*d*$ so that for all points $*X*$ on line image, $|*PX* - *QX*| ≤ *d*$. (It is guaranteed that $*d*$ exists and is unique.) They wish to find the line image passing through two distinct outposts $(*x*_{*i*}, *y*_{*i*})$ and $(*x*_{*j*}, *y*_{*j*})$ such that the difference of image relative to $*P*$ and $*Q*$ is minimized.

翻译中…

Input

翻译中…

The first line of the input contains two integers $*n*$ and $*a*$ ($2 ≤ *n* ≤ 100 000$, $1 ≤ *a* ≤ 10 000$) — 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*}| ≤ 10 000$). These points are distinct from each other as well as from $*P*$ and $*Q*$.

翻译中…

Output

翻译中…

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 image.

翻译中…

Note

翻译中…

In the first sample case, the only possible line image is $*y* = *x* - 1$. It can be shown that the point $*X*$ which maximizes $|*PX* - *QX*|$ is $(13, 12)$, with image, which is image.

翻译中…

In the second sample case, if we pick the points $(0, 1)$ and $(0,  - 3)$, we get image as $*x* = 0$. Because $*PX* = *QX*$ on this line, the minimum possible difference is $0$.

翻译中…

样例

Input #1
2 5
1 0
2 1
Output #1
7.2111025509
InputCopy OutputCopy
Input #2
3 6
0 1
2 5
0 -3
Output #2
0.0000000000
InputCopy OutputCopy
题目信息
题号
645G
时间限制
3 s
内存限制
256 MB
标签
二分
计算几何

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。