题目描述

There are $n$ circles on a plane. The $i$-th circle has a center at $(x_i,y_i)$ and a radius of $r_i$. These $n$ circles are pairwise non-intersecting, but they may be tangent (including internally or externally). There are two points $S$ and $T$ located on the arcs of these circles. $\texttt{Student A}$ starts at point S and can only travel along the circular arcs. Each circle has a parameter $v_i$, which represents the time per unit length of traveling along the arc of that circle. The goal is to find the minimum total time for $\texttt{Student A}$ to travel from point $S$ to point $T$ along the circular arcs.

输入格式

The first line contains five integers: $n(1≤n≤10^4), S_x,S_y, T_x,T_y( |S_x|,|S_y|,|T_x|,|T_y|≤10^9)$. Here, $n$ denotes the number of circles on the plane, $(S_x,S_y)$ represents the coordinates of the initial position $S$ of \texttt{Student A}, and $(T_x,T_y)$ denotes the coordinates of the target destination $T$.

The next $n$ lines each contain four positive integers $x_i,y_i,r_i,v_i( |x_i|,|y_i|≤10^9, 1≤r_i≤10^8, 0≤v_i≤10^5)$, representing the parameters of the $i$-th circle: the center coordinates are $(x_i,y_i)$, the radius is $r_i$, and the cost per unit length of traveling along the arc of this circle is $v_i$.

The data guarantees that points $S$ and $T$ are located on the arcs of two (possibly distinct) circles, no two circles intersect (they may be tangent, either internally or externally), and no two circles are entirely coincident (i.e., there are no two circles with identical center coordinates and equal radius).

输出格式

Output a single line containing a real number, which represents the minimum total cost for $\texttt{Student A}$ to travel from point $S$ to point $T$. If it is impossible to reach the destination, output $-1$.

The correctness of your answer is judged as follows:

If your determination of whether the destination is reachable (i.e., outputting $-1$ or a real number) differs from the standard answer, your answer is considered wrong.

If your determination matches the standard answer (both output $-1$ or both output a real number), and assuming your output is $Your\_Answer$ and the standard answer is $Answer$, your answer is considered correct if it satisfies either:$\frac{|Your\_Answer - Answer|}{Answer + 1} ≤ 10^{-6}$ or $|Your\_Answer-Answer| ≤ 10^{-6}$.

3 0 1 3 0
1 1 1 1
3 1 1 2
4 1 4 3

6.283185307179586

3 -10 0 0 0
0 0 10 2
0 0 8 3
0 4 4 5

-1

提示

:::align{center} :::

As shown in the example figure above, Circle 1 is denoted by the lowercase letter a, Circle 2 by b, and Circle 3 by c. One possible path achieving the minimum cost to travel from point $S$ to point $T$ is marked by the red path.