303334: CF645G. Armistice Area Apportionment

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 ![](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 $ .

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: