Description

Given a line segment and several points, find the maximum possible distance from a point on the segment to its nearest point among the given points.

Input Format

The first line contains two integers $n$ and $l$, meaning there are $n$ points in total, and the endpoints of the segment are $(0,0)$ and $(l,0)$.
Each of the next lines contains two integers $(x,y)$, describing the coordinates of a point. It is guaranteed that no two points have the same coordinates.
The points are given sorted in increasing order, with the $x$-coordinate as the primary key and the $y$-coordinate as the secondary key.

Output Format

Output the maximum distance.

This problem uses SPJ. Your answer is considered correct if the absolute error between your output and the standard answer does not exceed $10^{-3}$.

2 10
0 0
11 1

5.545455

Hint

Sample Explanation.

The point with the maximum distance lies at the intersection of the perpendicular bisector of two points and the line segment.

Constraints.

• For $25\%$ of the testdata, $n \leq 5000$.
• For $50\%$ of the testdata, $n \leq 10^5$.
• For $100\%$ of the testdata, $1 \leq n \leq 10^6$, $1 \leq l \leq 10^9$, $-10^9 \leq x_i,y_i \leq 10^9$.

Notes.

Translated from BalticOI 2012 Day1 T2. Mobile.

Translated by ChatGPT 5