Escape from Medusa's Maze

In the ancient legend of country P, the royal captain Little W has recovered the national treasure from the dragon Big Y but is now trapped in Medusa’s maze. The maze is represented by the Euclidean plane. Little W starts at (0,0) and must reach the exit at \( (p,q) \).

The maze is rigged with \( n \) flame traps. Each trap is described by three parameters \( (x,y,\theta) \). The trap is located at \( (x,y) \), and it fires a flame in the direction with an angle \( \theta \) (with respect to the positive \( x \)–axis). The flame is an infinitely long ray: formally, the flame from a trap at \( (x,y) \) covers all points of the form \[ (x,y) + t(\cos\theta,\sin\theta), \quad t>0. \] A path is unsafe if it passes through any point (other than allowed endpoints) that lies on any flame ray. Note that if a point coincides with a trap’s location and that trap’s flame is the only one covering that point, the point is considered safe.

Furthermore, due to the presence of the "Eye of Medusa" placed infinitely far in the negative \( x \)–direction, every segment of Little W’s path must have a strictly positive projection on the \( x \)–axis (i.e. the \( x \)–coordinate must strictly increase along the path).

Your task is to help Little W find the shortest safe path from (0,0) to \( (p,q) \) or determine that no such path exists. The path is a sequence of straight-line segments connecting a set of waypoints, where you are allowed to use the locations of flame traps as intermediate points. The length of a path is defined as the sum of Euclidean distances of its segments. If no safe path exists, output -1.

Input Constraints:

• The first line contains three numbers: \( p \), \( q \) and \( n \).
• The next \( n \) lines each contain three real numbers \( x\ y\ \theta \), representing a trap’s coordinates and the firing angle (in radians).

inputFormat

The first line contains three space‐separated numbers: \( p \), \( q \), and \( n \) (the number of flame traps).

Then follow \( n \) lines, each line containing three space‐separated real numbers \( x\ y\ \theta \), describing a flame trap at coordinate \( (x,y) \) with a flame firing in the direction \( \theta \) (in radians).

outputFormat

If a safe path exists, output the shortest distance with 6 decimal places. Otherwise, output -1.

sample

10 0 0

10.000000