你知道,现在很难在同一个地方举办一场有很多参与者和观众的表演。尽管如此,您并没有放弃制作车祸展示的梦想!您决定用遥控汽车取代真正的汽车,将活动命名为“遥控 Kaboom Show”并在线传输所有内容。
为了准备,你安排了一个竞技场——一个无限的二维场。您还购买了 $$$n$$$ 遥控汽车并将其安装在竞技场上。不幸的是,你买的车只能前进,不能左转、右转或掉头。因此,您还可以将汽车放置在您希望它们行驶的方向上。
正式来说,对于每辆车 $$$i$$$ ($$$1 \le i \le n$$$),您选择其初始位置 ($$$x_i, y_i$$$) 和方向向量 ($$$dx_i, dy_i$$$)。此外,每辆车都有每秒 $$$s_i$$$ 单位的恒定速度。因此,汽车 $$$i$$$ 启动后,它会从 ($$$x_i, y_i$$$) 向 ($$$dx_i, dy_i$$$) 方向以恒定速度 $$$s_i$$$ 移动。
该节目的目标是尽可能快地制造汽车碰撞!您注意到,在展会开始时启动每辆车通常根本不会产生任何碰撞。因此,您计划在某个时刻 $$$t_i$$$ 推出第 $$$i$$$ 辆车。您尚未选择 $$$t_i$$$,这尚未决定。请注意,$$$t_i$$$ 不必是整数,并且对于任何 $$$i、j$$$,$$$t_i$$$ 可以等于 $$$t_j$$$。
演出于时间 $$$0$$$ 开始。当两辆车 $$$i$$$ 和 $$$j$$$ ($$$i \ne j$$$) 碰撞时(即同时到达同一坐标),节目结束。演出时长是指从开始到结束的时间。
通过选择所有 $$$t_i$$$ 可以安排最快的崩溃是什么?如果可以安排崩溃,则打印尽可能短的演出持续时间。否则,报告说这是不可能的。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 25000$$$) — 汽车数量。
接下来的 $$$n$$$ 行包含五个整数 $$$x_i$$$, $$$y_i$$$, $$$dx_i$$$, $$$dy_i$$$, $$$s_i$$$ ($$$-10^3 \le x_i, y_i \le 10^3$$$; $$$1 \le |dx_i| \le 10^3$$$; $$$1 \le |dy_i| \le 10^3$$$; $$$1 \le s_i \le 10^3$$$) — 第 $$$i$$$ 车的初始位置、其方向向量和速度。
保证所有汽车都从不同的位置开始(即 $$$(x_i, y_i) \neq (x_j, y_j)$$$ for $$$i \neq j$$$)。
输出
如果可以通过选择所有 $$$t_i$$$ 来安排崩溃,请打印最短的演出持续时间。否则,打印“No show :(”。
如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入 #1
4 3 -1 -1 1 2 2 3 -3 -2 10 -4 2 1 -2 1 -2 -2 -1 2 4
输出 #1
0.585902082262898
输入 #2
2 -1 1 -1 1 200 1 1 1 5 200
输出 #2
No show :(
注意
这是第一个示例的图片:
撞车速度最快的汽车是 $$$2$$$ 和 $$$4$$$ 车。让我们在 $$$0$$$ 启动汽车 $$$2$$$,在 $$$0.096762$$$ 左右启动汽车 $$$4$$$,在任意时间启动汽车 $$$1$$$ 和 $$$3$$$。这样,$$$2$$$ 和 $$$4$$$ 之间的汽车就会在 $$$0.585902$$$ 左右相撞。这是碰撞瞬间的样子:
这是第二个示例的图片: