Problem Description

Country A and Country B are at war. The war is extremely brutal, and both countries are deeply short of resources, so they decide to hold peace talks.

An important part of the talks is to determine the border between the two countries. On a plane, the military centers of Country A and Country B are located at $A=(X_A, Y_A)$ and $B=(X_B, Y_B)$. There are also $n$ landmark buildings on the plane, located at $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$.

For convenience of construction, they plan to choose the line segment connecting two landmark buildings as the border. However, both sides suspect that the other side might secretly restart the war after the treaty is signed. Clearly, if at some point on the border, the difference between its distances to the two military centers is too large, then the side that is closer can quickly dispatch troops from its military center to attack that point, while the farther side will need much more time to reinforce it. Therefore, they define the danger value of a border as the maximum, over all points on this border, of the absolute difference between the distances from that point to the two military centers (that is, for each point $X$ on the line segment, take $|AX-BX|$, and then take the maximum over all such $X$).

Both countries want to choose a border with the minimum possible danger value. But their large electronic devices (such as supercomputers capable of $10^{10000}$ operations per second) were mostly destroyed in the war, leaving only ordinary computers that can perform about $10^8$ to $10^{10}$ operations per second. The high command also does not want to wait too long. You, as the widely recognized top algorithm expert at the time, are asked to solve this problem quickly. You only need to compute this minimum danger value.

Input Format

The first line contains five integers $n, X_A, Y_A, X_B, Y_B$.

The next $n$ lines each contain two integers. The $i$-th line gives $x_i, y_i$.

Output Format

Output one floating-point number in one line, representing the minimum danger value. The error must not exceed $10^{-6}$. You may output more or fewer than $6$ digits after the decimal point.

3 -5 0 5 0
2 1
1 0
2 2

7.2111025509

Hint

Constraints

For all data, $1 \le n \le 100000$, and the absolute values of all coordinates are at most $10^9$.

Translated by ChatGPT 5