题目描述

平面上有 $n$ 个圆。第 $i$ 个圆的圆心坐标为 $(x_i,y_i)$，半径为 $r_i$。这 $n$ 个圆两两之间互不相交，但可以相切（包括内切或外切）。给定位于这些圆的圆弧上的两个点 $S$ 与 $T$。同学 A 从点 $S$ 出发，只能沿着圆弧行走。每个圆具有一个参数 $v_i$，表示在该圆的圆弧上行走单位长度所需的时间。目标为求 同学 A 沿着圆弧从点 $S$ 行至点 $T$ 所需的最短总时间。

输入格式

第一行包含五个整数：$n$（$1\le n\le 10^4$），$S_x,S_y, T_x,T_y$（$|S_x|,|S_y|,|T_x|,|T_y|\le 10^9$）。其中 $n$ 表示平面上圆的个数，$(S_x,S_y)$ 表示 同学 A 的初始位置 $S$ 的坐标，$(T_x,T_y)$ 表示目标位置 $T$ 的坐标。

接下来的 $n$ 行，每行包含四个正整数 $x_i,y_i,r_i,v_i$（$|x_i|,|y_i|\le 10^9$，$1\le r_i\le 10^8$，$0\le v_i\le 10^5$），表示第 $i$ 个圆的参数：圆心坐标为 $(x_i,y_i)$，半径为 $r_i$，在该圆圆弧上行走单位长度的代价为 $v_i$。

数据保证点 $S$ 与点 $T$ 位于某两个（可以是同一个）圆的圆弧上，任意两圆之间均不相交（可以内切或外切），且不存在完全重合的两个圆（即不存在圆心坐标相同且半径相等的两个圆）。

输出格式

输出一行一个实数，表示 同学 A 从点 $S$ 行至点 $T$ 的最小总代价。若无法抵达目的地，则输出 $-1$。

你的答案的正确性按以下规则评判：

若你对于目的地是否可达的判断（即输出 $-1$ 还是实数）与标准答案不同，则你的答案被视为错误。

若你的判断与标准答案一致（均输出 $-1$ 或均输出实数），假设你的输出为 $Your\_Answer$，标准答案为 $Answer$，若满足 $\frac{|Your\_Answer - Answer|}{Answer + 1} \le 10^{-6}$ 或 $|Your\_Answer-Answer| \le 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} :::

如上图样例所示，圆 1 用小写字母 a 标示，圆 2 用 b 标示，圆 3 用 c 标示。图中红色路径标示了一条从点 $S$ 行至点 $T$ 的、达到最小代价的可行路径。

翻译由 DeepSeek V3.2 完成