{"raw_statement":[{"iden":"statement","content":"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."},{"iden":"input","content":"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_ ≤ 104). 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 105. 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_)."},{"iden":"output","content":"Print a single number with absolute or relative error no more than 10 - 4 — the minimum required speed of Pedalny in meters per second."},{"iden":"examples","content":"Input\n\n0 0 10 0\n1\n5 -5 4.71238 1\n0\n\nOutput\n\n4.2441\n\nInput\n\n0 0 10 0\n1\n5 -5 4.71238 1\n1\n\nOutput\n\n0.0000"}],"translated_statement":[{"iden":"statement","content":"Vasya 玩《坦克平面》游戏。游戏中的坦克总是试图互相消灭。但你的 \"Pedalny\" 不同……他只需要在平面上从点 #cf_span[A] 沿直线行驶到点 #cf_span[B]。不幸的是，同一平面上有 #cf_span[n] 个敌方坦克。我们将所有坦克视为点。在初始时刻，Pedalny 位于点 #cf_span[A]。敌方坦克希望立即摧毁它，但起初它们的炮塔指向其他方向。具体而言，对于每个坦克，我们知道其炮塔的初始旋转角度 #cf_span[ai]（相对于 #cf_span[OX] 轴逆时针方向的弧度角）以及炮塔的最大旋转速度 #cf_span[wi]（弧度/秒）。如果在任意时刻，某个坦克的炮塔恰好对准了 Pedalny 坦克，则该敌方会开火，且从不miss。Pedalny 最多能承受 #cf_span[k] 发射击。装弹耗时很长，因此我们可以假设每个敌方最多只会开一枪。你的任务是确定 Pedalny 要到达点 #cf_span[B] 所需的最小速度 #cf_span[v]。假设 Pedalny 能瞬间加速到速度 #cf_span[v]，并且前 #cf_span[k] 发击中不会降低其速度，也不会改变其坐标。\n\n第一行包含 4 个数字——点 #cf_span[A] 和 #cf_span[B] 的坐标（单位：米），两点不重合。第二行给出数字 #cf_span[n]（#cf_span[1 ≤ n ≤ 104]），表示敌方坦克的数量。接下来的 #cf_span[n] 行每行包含一个敌方坦克的坐标 #cf_span[xi, yi] 及其参数 #cf_span[ai] 和 #cf_span[wi]（#cf_span[0 ≤ ai ≤ 2π]，#cf_span[0 ≤ wi ≤ 100]）。数字 #cf_span[ai] 和 #cf_span[wi] 最多包含小数点后 5 位。所有坐标均为整数，绝对值不超过 #cf_span[105]。敌方坦克可以以不超过 #cf_span[wi] 的角速度顺时针或逆时针旋转炮塔。保证每个敌方坦克至少需要 #cf_span[0.1] 秒才能对准线段 #cf_span[AB] 上的任意一点，且每个敌方坦克到直线 #cf_span[AB] 的距离不少于 #cf_span[0.1] 米。最后一行给出数字 #cf_span[k]（#cf_span[0 ≤ k ≤ n]）。\n\n输出一个数字，绝对误差或相对误差不超过 #cf_span[10 - 4] —— Pedalny 所需的最小速度（单位：米/秒）。"},{"iden":"input","content":"第一行包含 4 个数字——点 #cf_span[A] 和 #cf_span[B] 的坐标（单位：米），两点不重合。第二行给出数字 #cf_span[n]（#cf_span[1 ≤ n ≤ 104]），表示敌方坦克的数量。接下来的 #cf_span[n] 行每行包含一个敌方坦克的坐标 #cf_span[xi, yi] 及其参数 #cf_span[ai] 和 #cf_span[wi]（#cf_span[0 ≤ ai ≤ 2π]，#cf_span[0 ≤ wi ≤ 100]）。数字 #cf_span[ai] 和 #cf_span[wi] 最多包含小数点后 5 位。所有坐标均为整数，绝对值不超过 #cf_span[105]。敌方坦克可以以不超过 #cf_span[wi] 的角速度顺时针或逆时针旋转炮塔。保证每个敌方坦克至少需要 #cf_span[0.1] 秒才能对准线段 #cf_span[AB] 上的任意一点，且每个敌方坦克到直线 #cf_span[AB] 的距离不少于 #cf_span[0.1] 米。最后一行给出数字 #cf_span[k]（#cf_span[0 ≤ k ≤ n]）。"},{"iden":"output","content":"输出一个数字，绝对误差或相对误差不超过 #cf_span[10 - 4] —— Pedalny 所需的最小速度（单位：米/秒）。"},{"iden":"examples","content":"输入0 0 10 015 -5 4.71238 10输出4.2441输入0 0 10 015 -5 4.71238 11输出0.0000"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ A, B \\in \\mathbb{R}^2 $ be the start and end points of Pedalny’s path.  \nLet $ n \\in \\mathbb{Z}_{\\geq 0} $ be the number of enemy tanks.  \nFor each enemy tank $ i \\in \\{1, \\dots, n\\} $:  \n- Let $ P_i = (x_i, y_i) \\in \\mathbb{R}^2 $ be its position.  \n- Let $ \\alpha_i \\in [0, 2\\pi) $ be its initial turret angle (relative to the $ x $-axis, counterclockwise).  \n- Let $ w_i \\in [0, 100] $ be its maximum angular speed (radians per second).  \n\nLet $ k \\in \\{0, \\dots, n\\} $ be the maximum number of shots Pedalny can survive.  \n\nLet $ \\ell = \\|B - A\\| $ be the Euclidean length of the segment $ AB $.  \n\nLet $ \\theta_i(v) \\in [0, 2\\pi) $ be the angle of the vector from $ P_i $ to Pedalny’s position at time $ t $ along the path from $ A $ to $ B $, assuming Pedalny moves at constant speed $ v > 0 $.  \n\nDefine the **aiming time** for enemy $ i $ as the earliest time $ t_i(v) \\geq 0 $ such that the turret can rotate from $ \\alpha_i $ to $ \\theta_i(v) $ within angular speed $ w_i $, i.e.,  \n$$\nt_i(v) = \\frac{d_i(v)}{w_i}, \\quad \\text{where} \\quad d_i(v) = \\min_{\\delta \\in \\mathbb{Z}} \\left| \\theta_i\\left(\\frac{\\ell \\cdot t_i(v)}{\\ell}\\right) - \\alpha_i + 2\\pi \\delta \\right|\n$$  \nis the minimal angular distance (modulo $ 2\\pi $) between the initial turret direction and the direction to Pedalny at the moment it passes the point at distance $ vt_i(v) $ from $ A $ along $ AB $.  \n\n*(Note: $ \\theta_i(v) $ is a function of position along the path, hence of $ t $, and $ t_i(v) $ is implicitly defined by the condition that Pedalny reaches position $ A + \\frac{vt_i(v)}{\\ell}(B - A) $ at time $ t_i(v) $.)*  \n\n**Constraints**  \n1. $ \\|B - A\\| > 0 $  \n2. $ 1 \\leq n \\leq 10^4 $  \n3. $ 0 \\leq k \\leq n $  \n4. For all $ i $, the perpendicular distance from $ P_i $ to line $ AB $ is $ \\geq 0.1 $  \n5. For all $ i $, the minimal time required to aim at any point on $ AB $ is $ \\geq 0.1 $ seconds  \n6. $ w_i \\geq 0 $, $ \\alpha_i \\in [0, 2\\pi) $, all coordinates are integers with absolute value $ \\leq 10^5 $\n\n**Objective**  \nFind the minimum speed $ v^* > 0 $ such that **at most $ k $** enemy tanks can aim at Pedalny along his path, i.e.,  \n$$\n\\left| \\left\\{ i \\in \\{1, \\dots, n\\} \\mid t_i(v^*) \\leq \\frac{\\ell}{v^*} \\right\\} \\right| \\leq k\n$$  \nwhere $ \\frac{\\ell}{v^*} $ is the total travel time of Pedalny from $ A $ to $ B $.  \n\nEquivalently, define for each enemy $ i $ the **critical speed** $ v_i $ such that $ t_i(v_i) = \\frac{\\ell}{v_i} $. Then $ v^* $ is the smallest speed such that the number of enemies with $ v_i \\geq v^* $ is at most $ k $.  \n\nThus:  \n$$\nv^* = \\inf \\left\\{ v > 0 \\ \\middle| \\ \\left| \\left\\{ i \\mid v_i \\geq v \\right\\} \\right| \\leq k \\right\\}\n$$  \nwhere $ v_i $ satisfies:  \n$$\n\\frac{d_i(v_i)}{w_i} = \\frac{\\ell}{v_i} \\quad \\Rightarrow \\quad v_i = \\frac{\\ell \\cdot w_i}{d_i(v_i)}\n$$  \nand $ d_i(v_i) $ is the minimal angular distance from $ \\alpha_i $ to the direction from $ P_i $ to the point on $ AB $ at distance $ \\ell \\cdot \\frac{t_i(v_i)}{\\ell} = v_i t_i(v_i) $ from $ A $.  \n\n*(This is a fixed-point equation in $ v_i $, but computationally, one may binary search on $ v $ and for each $ v $, compute for each enemy whether they can aim before Pedalny passes.)*","simple_statement":null,"has_page_source":false}