Plane of Tanks

题意翻译

### 题目描述 你正在玩坦克大战。游戏中的坦克试图摧毁别的坦克，但是你面临的任务不像 [那样](https://www.luogu.com.cn/problem/CF175D) 复杂。你只需要从地图的点 $A$ 把坦克开一条直线到点 $B$。不幸的是，在地图上有一些敌军坦克。我们可以把这些所有的坦克视作点。在一开始你的坦克在 $A$ 点，敌军坦克想要立即击毁它，但是它们的炮塔初始位置在其它的方向上。具体来说，对于每台坦克，我们知道它们的初始炮塔角度 $a_i(rad)$，表示炮塔方向和 $x$ 轴逆时针方向的夹角和它们的最大转速，用 $w_i(rad/s)$ 表示。任何时间点，如果一个敌方坦克的炮管对准了你的坦克，它会立即开火并且准确度达 $100\%$，也就是每炮必中。你的坦克的装甲可以抵挡 $k$ 次伤害。装填弹药耗时很长，所以你可以认为每台敌军坦克只会造成一次伤害。你的任务是计算出你的坦克的最低速度。无需考虑被击中会导致你坦克的速度降低或者坦克移位。 ### 输入格式 第一行包括 $4$ 个数字，分别表示 $A,B$ 两个点的坐标（单位是米），保证 $A\ne B$。 第二行一个整数 $n$，表示敌方坦克的数目。 接下来的 $n$ 行（$3\sim n+2$ 行），每行四个整数，分别表示对应编号坦克的坐标 $(x_i,y_i)$ 和 $a_i(rad),w_i(rad/s)$。敌方坦克可以以顺时针或逆时针方向以不超过 $w_i$ 的角速度运动。 最后一行一个整数 $k$。 ### 输出格式 输出一个表示你的坦克的最低速度。单位米每秒，保留四位小数。 ### 数据范围 对于所有数据，$a_i$ 和 $w_i$ 在小数点后最多有 $5$ 位小数。所有的坐标都是整数。数据保证任何一台敌军坦克将会花费至少 $0.1$ 秒钟的时间来瞄准（注意此处不是说炮塔转过去然后再瞄准，而是炮塔转过去的时间）线段 $AB$ 上的任意一点且敌方坦克与线段 $AB$ 的距离不近于 $0.1$ 米。 对于所有数据，$1\leqslant n\leqslant 10^4,0\leqslant |x_i|,|y_i|\leqslant 10^5,0\leqslant a_i\leqslant2\pi,0\leqslant w_i\leqslant 100,0\leqslant k\leqslant n$。

题目描述

Vasya plays the Plane of Tanks. The tanks in this game keep trying to finish each other off. But your "Pedalny" is not like that... He just needs to drive in a straight line from point $ A $ to point B on the plane. Unfortunately, on the same plane are $ n $ enemy tanks. We shall regard all the tanks as points. At the initial moment of time Pedalny is at the point $ A $ . Enemy tanks would be happy to destroy it immediately, but initially their turrets are tuned in other directions. Specifically, for each tank we know the initial rotation of the turret $ a_{i} $ (the angle in radians relative to the $ OX $ axis in the counterclockwise direction) and the maximum speed of rotation of the turret $ w_{i} $ (radians per second). If at any point of time a tank turret will be aimed precisely at the tank Pedalny, then the enemy fires and it never misses. Pedalny can endure no more than $ k $ shots. Gun reloading takes very much time, so we can assume that every enemy will produce no more than one shot. Your task is to determine what minimum speed of $ v $ Pedalny must have to get to the point $ B $ . It is believed that Pedalny is able to instantly develop the speed of $ v $ , and the first $ k $ shots at him do not reduce the speed and do not change the coordinates of the tank.

输入输出格式

输入格式

The first line contains 4 numbers – the coordinates of points $ A $ and $ B $ (in meters), the points do not coincide. On the second line number $ n $ is given ( $ 1<=n<=10^{4} $ ). It is the number of enemy tanks. Each of the following $ n $ lines contain the coordinates of a corresponding tank $ x_{i},y_{i} $ and its parameters $ a_{i} $ and $ w_{i} $ ( $ 0<=a_{i}<=2π $ , $ 0<=w_{i}<=100 $ ). Numbers $ a_{i} $ and $ w_{i} $ contain at most 5 digits after the decimal point. All coordinates are integers and their absolute values do not exceed $ 10^{5} $ . Enemy tanks can rotate a turret in the clockwise as well as in the counterclockwise direction at the angular speed of not more than $ w_{i} $ . It is guaranteed that each of the enemy tanks will need at least $ 0.1 $ seconds to aim at any point of the segment $ AB $ and each of the enemy tanks is posistioned no closer than $ 0.1 $ meters to line $ AB $ . On the last line is given the number $ k $ ( $ 0<=k<=n $ ).

输出格式

Print a single number with absolute or relative error no more than $ 10^{-4} $ — the minimum required speed of Pedalny in meters per second.

输入输出样例

输入样例 #1

0 0 10 0
1
5 -5 4.71238 1
0

输出样例 #1

4.2441

输入样例 #2

0 0 10 0
1
5 -5 4.71238 1
1

输出样例 #2

0.0000