Description

As is well known, not far from Country P lurks the great dragon Da Y. Legend has it that in ancient times, the great dragon Da Y stole Country P’s national treasure and hid it in its lair, attracting all adventurers of Country P to try to take it back—especially Captain Xiao W of the Royal Guards. With the help of Country P’s Quantum Technology Laboratory, Captain Xiao W used quantum teleportation to enter the dragon’s treasury and successfully retrieved the national treasure. But at that moment, the dragon’s offensive barrier activated and trapped Xiao W in Medusa’s Labyrinth.

Trapped at $(0, 0)$, Captain Xiao W quickly examined the structure of Medusa’s Labyrinth and found that the exit is at $(p, q)$. The great dragon Da Y has placed $n$ flame-breath devices in the labyrinth. Each device is described by three parameters $(x, y, \theta)$, indicating that the device is at coordinate $(x, y)$ on the plane, and that the direction of its breath has inclination angle $\theta$ relative to the positive $x$-axis. Owing to the dragon’s power, each flame breath is an infinite ray, and Captain Xiao W may not pass through any ray covered by a flame breath (note that the device’s own coordinate is passable if it is not covered by other flame breath). Meanwhile, an Eye of Medusa is placed at negative infinity along the $x$-direction, which forces Captain Xiao W to always move “favoring” the positive $x$-direction (that is, the projection of his movement direction onto the positive $x$-direction must be strictly positive; it cannot be negative or zero), otherwise he will be instantly petrified and unable to escape.

In a panic, Captain Xiao W must escape Medusa’s Labyrinth before the great dragon Da Y catches him. He turns to the think tank of Country P for help. As the head of the think tank, you must find the shortest safe path to the exit of the labyrinth.

Input Format

The first line contains three integers $n, p, q$, denoting the total number of flame-breath devices and the exit coordinates.

Each of the next $n$ lines contains two integers and one real number $(x, y, \theta)$, denoting the device’s coordinates and the inclination angle of its flame breath relative to the positive $x$-axis.

Output Format

Output a single real number on one line, the length of the shortest path. Your answer is accepted if its relative error does not exceed $10^{-8}$ (i.e., if $\frac{|a - o|}{a} \le 10^{-8}$, where $a$ is the standard answer and $o$ is your output).

7 20 -5
4 3 -2.875
5 7 -1.314
10 -2 0.666
16 1 -1.571
16 1 1.571
23 -3 -2.130
14 -5 3.073

33.3380422500

7 20 0
5 2 1.155
5 2 1.987
5 2 -1.571
11 -4 1.765
11 -4 1.377
15 -4 1.765
15 -4 1.377

24.2735704188

Hint

[Sample Explanation]

$30\%$ of the testdata satisfy $n \le 300$; $60\%$ of the testdata satisfy $n \le 2000$; $80\%$ of the testdata satisfy $n \le 10^5$; $100\%$ of the testdata satisfy $0 \le n, p, |q|, |x|, |y| \le 10^6;\ \theta \in [-\pi, \pi]$. It is guaranteed that at least one valid path exists, and neither the start point nor the end point lies on any flame ray.

Translated by ChatGPT 5