21893번 - Road Building 서브태스크스페셜 저지다국어

문제

The burger eating contest is coming! The contest is taking place at two different cities. But there was a slight miscalculation --- there is no direct road between these cities across the forest. To save enough time organizers decided to build a direct road with maximum width through the forest without cutting any trees. Moreover, it was decided to leave at least one tree on both sides of the road.

For simplicity, let's represent each tree as a circle on plane with Cartesian coordinates. Build a road of infinite length and maximum width parallel to straight line, that passes through two given points.

입력

First line contains four integers $x_s,ドル $y_s,ドル $x_f$ and $y_f$ --- coordinates of points $(x_s, y_s)$ and $(x_f, y_f)$ that the line passes through.

Second line contains single integer $n$ --- number of trees in the forest (2ドル \le n \le 2 \cdot 10^5$). There are no intersecting trees, but they can touch each other.

Each of the next $n$ lines contains three integers $x_i,ドル $y_i$ and $r_i$ --- coordinates of the center and radius of $i$-th tree (1ドル \le r_i \le 10^9$).

All coordinates' absolute values don't exceed 10ドル^9$.

출력

Output maximum width of the road parallel to straight line, that passes through points $(x_s, y_s)$ and $(x_f, y_f)$. There should be at least one tree on both sides of the road. The road may touch the trees, but not intersect them. If there is no such road, output 0.

Your answer will be accepted, if it's absolute or relative error doesn't exceed 10ドル^{-6}$. Formally speaking, if your answer is $a$ and jury's is $b,ドル then it will be accepted if $\frac {|a - b|}{\max(1, b)} \le 10^{-6}$.

제한

서브태스크

힌트