4052: 「AHOI / HNOI2017」队长快跑
内存限制:256 MB
时间限制:3.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
众所周知,在 P 国外不远处盘踞着巨龙大 Y。传说中,在远古时代,巨龙大 Y 将 P 国的镇国之宝窃走并藏在了其巢穴中,这吸引着整个 P 国的所有冒险家前去夺回,尤其是皇家卫士队的队长小 W。在 P 国量子科技实验室的帮助下,队长小 W 通过量子传输进入了巨龙大 Y 的藏宝室,并成功夺回了镇国之宝。但此时巨龙布下的攻击性防壁启动,将小 W 困在了美杜莎的迷宫当中。
被困在迷宫 $(0,0)$ 处的队长小 W 快速观察了美杜莎的迷宫的构造,发现迷宫的出口位于 $(p, q)$ 处。巨龙大 Y 在迷宫当中布置了 $n$ 个火焰吐息机关,每个机关可以用三个参数 $(x, y, \theta)$ 表示,分别指明机关位于平面的坐标 $(x, y)$,以及火焰吐息的方向相对于 $x$ 轴正方向的倾角 $\theta$。巨龙强大的力量使得火焰吐息有无穷长,且队长小 W 不能通过被火焰吐息覆盖的射线(注意,机关所处的坐标若没有被其他火焰吐息覆盖,则是可以通过的)。同时,迷宫在沿 $x$ 轴负方向无穷远的地方放置了美杜莎之眼,使得队长小 W 必须倾向于向 $x$ 轴正方向行动(即队长小 W 的移动方向在 $x$ 轴正方向上的投影必须为正,不能是负数或零),否则队长小 W 将被瞬间石化而无法逃离。
心急如焚的队长小 W 需要趁着巨龙大 Y 还没将其抓住前逃离美杜莎的迷宫,所以他立马向 P 国智囊团求助,作为智囊团团长的你,一定可以帮队长小 W 找出安全逃至迷宫出口的最短道路。
输入
第一行为三个整数 $n, p, q$,分别表示火焰吐息机关总数以及出口坐标。
接下来 $n$ 行,每行两个整数与一个实数 $x, y, \theta$,分别表示机关所处的坐标以及火焰吐息的关于 $x$ 轴正方向的倾角。
输出
输出文件仅包含一行一个小数,表示最短道路的长度。当你的答案和标准答案的相对误差不超过 $10^{−8}$ 时(即 $\frac {|a - o|} a \le 10^{-8}$ 时,其中 $a$ 是标准答案,$o$ 是输出)认为你的答案正确。
样例输入 复制
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
提示
输入样例2
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
输出样例2
24.2735704188
数据范围:对于 $30\%$ 的数据,$n\le 300$; 对于 $60\%$ 的数据,$n\le 2000$; 对于 $80\%$ 的数据,$n\le 10^5$; 对于 $100\%$ 的数据,$0\le n, p, |q|, |x|, |y| \le {10}^6, \theta\in [-\pi, \pi)$。 数据保证至少存在一条合法路径,且起点和终点均不会被火焰路径覆盖。