← 返回题目列表

Codeforces · 793/C

C. 老鼠问题

中文机器翻译题面 查看原题

分析师伊戈尔在工作中睡着了,做了一个奇怪的梦。梦中他的办公桌上挤满了电脑鼠标,他买了一个捕鼠器来捕捉它们。

桌子可以被认为是一个无限平面,那么捕鼠器就是一个边与轴平行的矩形,其相对边位于点(x1,y1)和(x2,y2)。

伊戈尔想要抓住所有老鼠。 Igor 分析了它们的行为,发现每只老鼠都以匀速沿直线移动,第 i 个老鼠的速度等于 (vix, viy),这意味着老鼠的 x 坐标每秒增加 vix 个单位,而 y 坐标则每秒增加 viy 个单位。捕鼠器最初打开,以便老鼠能够在桌子上自由移动。伊戈尔可以随时关闭捕鼠器,捕捉严格在捕鼠器内的所有老鼠。

伊戈尔的工作量很大,所以他在梦里也很忙,他要求你写一个程序,根据给定的捕鼠器坐标,老鼠的初始坐标和它们的速度,确定他最早能够抓住所有老鼠的时刻。请注意,伊戈尔只能关闭捕鼠器一次。

输入

第一行包含单个整数 n (1 ≤ n ≤ 100 000) — 桌上电脑鼠标的数量。

第二行包含四个整数 x1、y1、x2 和 y2 (0 ≤ x1 ≤ x2 ≤ 100 000),(0 ≤ y1 ≤ y2 ≤ 100 000) – 捕鼠器对角的坐标。

接下来的 n 行包含有关小鼠的信息。

其中第 i 行包含四个整数 rix、riy、vix 和 viy,(0 ≤ rix, riy ≤ 100 000, - 100 000 ≤ vix, viy ≤ 100 000),其中 (rix, riy) 是鼠标的初始位置,(vix, viy) 是鼠标的速度。

输出

在唯一的一行中打印最小可能的非负数 t ,这样如果 Igor 在从开始的 t 秒处关闭捕鼠器,那么所有的老鼠都严格在捕鼠器内。如果没有这样的t,则打印-1。

如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

正式来说,让您的答案为 a,陪审团的答案为 b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,则认为您的答案是正确的。

示例

输入 #1

4
7 7 9 8
3 5 7 5
7 5 2 4
3 3 7 8
6 6 3 2

输出 #1

0.57142857142857139685

输入 #2

4
7 7 9 8
0 3 -5 4
5 0 5 4
9 9 -1 -6
10 5 -7 -10

输出 #2

-1

注意

这是第一个样本的图片

点 A、B、C、D - 鼠标的起始位置,线段是它们的路径。

然后,第一次当所有鼠标都在矩形中时,它看起来像这样:

这是第二个示例的图片

A、D、B 点永远不会进入矩形。