题目描述

$N$ 艘渔船用一张弹性渔网围住了一群巨大而危险的鱼。初始时，所有船都位于一个凸多边形的顶点上，渔网被拉紧，使得船位于渔网内侧，也就是鱼所在的一侧。每艘船都在拉紧渔网，且凸多边形相邻顶点之间的渔网是一条直线。船不能移动到渔网之外。

一艘船只有在真正拉紧渔网时才是安全的，也就是说，它必须位于所有船的凸包的某个顶点上。因为鱼不希望渔网改变位置，所以它们不会攻击这样的船。但是，如果某艘船位于渔网围成的多边形内部，或者位于其某条边上但不是顶点，它就会立刻被鱼攻击并摧毁。

如前所述，渔网是弹性的。如果一艘船改变位置，那么凸包，也就是渔网的形状，可能会发生变化，顶点也可能改变。

当然，船本来更愿意停在原来的位置，等待专门捕捉这种危险鱼类的渔船到来。不幸的是，水流和风会使一些船移动。实际上，每艘船都按时间做线性运动：在初始时刻 $t=0$，某艘船位于坐标 $(S_x,S_y)$；在时刻 $t$，它位于

在这种运动过程中，凸包（即弹性渔网的形状）会变化，一些不再处于凸包顶点的船会被鱼摧毁。

请编写程序 boats，对每艘船判断它是否会被摧毁。如果会被摧毁，则计算它被摧毁的精确时间。

输入格式

第一行输入一个正整数 $N$，表示船的数量。

接下来 $N$ 行，每行输入四个整数，用单个空格分隔：

Sx Sy Vx Vy

表示当前船的初始坐标以及速度。

输入船的顺序与它们初始在凸多边形顶点上的排列顺序一致，即按逆时针顺序给出。

输出格式

对于每艘船，按照输入顺序各输出一行，包含一个实数：

• 若该船会被摧毁，输出它被摧毁的时间 $t>0$；
• 若该船会幸存，输出 -1.0。

如果每个输出数字的绝对误差或相对误差小于 $10^{-5}=0.00001$，则认为答案正确。

误差定义：

• 绝对误差：$\operatorname{abs}(A-B)<\varepsilon$；
• 相对误差：$\operatorname{abs}(A-B)/A<\varepsilon$。

数据范围

• $3 \le N \le 100000$；
• $-10^9 \le S_x,S_y \le 10^9$；
• $-200 \le V_x,V_y \le 200$；
• 所有船的 $S_x,S_y,V_x,V_y$ 均为整数；
• 若某艘船会被摧毁，其摧毁时间位于 $10^{-7}$ 到 $10^{12}$ 之间；
• 对任意 $t \ge 0$，渔网围成的面积始终严格为正；
• 任意两艘船不会“相撞”，即不存在某个时刻两艘船位于同一点。

样例

输入

4
0 0 0 0
1 0 1 0
1 1 0 0
0 1 0 1

输出

-1.0000000000
-1.0000000000
1.0000000000
-1.0000000000

样例解释

初始时，船 $1,2,3,4$ 位于边长为 $1$ 的正方形四个顶点。船 $1$ 和船 $3$ 保持静止，船 $2$ 沿 $x$ 轴向右以速度 $1$ 移动，船 $4$ 沿 $y$ 轴向上以速度 $1$ 移动。

在经过 $1$ 个单位时间之前，船 $2$ 和船 $4$ 的位置使得船 $3$ 仍然拉紧渔网，即船 $3$ 仍是四艘船凸包的顶点。

在时刻 $t=1$，船 $2,3,4$ 共线，船 $3$ 不再是顶点，因此会被鱼摧毁。其他三艘船会继续拉紧渔网，不会被摧毁。

【图片说明：原题样例解释旁有一张船只位置与编号示意图，请后续自行加入。】