题目描述

现在是公元 2390 年 11 月 1 日，星期日。Eddy 刚刚当选世界议会成员。

这是一份有趣而责任重大的工作，Eddy 也很期待开始履职，但他遇到了一个问题：Eddy 非常热爱运动，尤其喜欢慢跑。从小时候起，他每天至少都会慢跑 30 分钟。成为议员后，他的空闲时间将比以前当教师时更少。他该怎样挤出慢跑时间呢？

Eddy 决定在上班途中慢跑。由于他的家离议会大楼很远，他希望把慢跑和公共交通结合起来。

首都唯一的公共交通工具是移动步道。每条线路由两条方向相反、速度相同的直线移动步道组成，步道速度为 $v_1>0$。

这些步道非常长且相对狭窄，因此在本题中，每条线路可以视为平面上的一条无限直线。

对第 $i$ 条步道线路，还给定两个数：

• $T_i^+$：登上该步道所需的时间；
• $T_i^-$：离开该步道所需的时间。

穿过一条步道本身不需要额外时间。

如果两条步道线路相交，那么在交点处从第 $i$ 条步道换乘到第 $j$ 条步道，所需时间恰好为

实际上，这些位置建有专用桥梁，因此两条线路并不会发生物理冲突。

Eddy 在步道上也会继续慢跑。若他在静止地面上的慢跑速度为 $v_2>0$，那么他沿移动步道运动时，相对于地面的速度为

请你找出一条从 Eddy 家到议会大楼的最短用时路线。路线由若干条线段组成，其中一些线段可以位于已有的移动步道上。

输入格式

第一行包含一个整数 $N$（$0\le N\le 50$），表示城市中移动步道线路的数量。

第二行包含六个实数：

x1 y1 x2 y2 v1 v2

其中：

• $(x_1,y_1)$ 是 Eddy 家的坐标；
• $(x_2,y_2)$ 是议会大楼的坐标；
• $v_1$ 是移动步道速度；
• $v_2$ 是 Eddy 在静止地面上的慢跑速度。

接下来 $N$ 行，每行包含六个实数：

xi1 yi1 xi2 yi2 Ti+ Ti-

其中：

• $(x_{i1},y_{i1})$ 与 $(x_{i2},y_{i2})$ 是第 $i$ 条步道所在直线上的两个不同点；
• $T_i^+$ 是登上该步道所需时间；
• $T_i^-$ 是离开该步道所需时间。

数据满足：

• 所有坐标的绝对值均不超过 $10000$；
• $1\le v_1,v_2\le 100$；
• $0\le T_i^+,T_i^-\le 10$；
• 所有步道位于互不相同的直线上；
• 起点 $(x_1,y_1)$ 与终点 $(x_2,y_2)$ 均不在任何步道上。

输出格式

第一行输出一个实数 $T$，表示最短旅行时间。

第二行输出一个整数 $M$（$0<M\le 300$），表示最优路线由多少条线段组成。

接下来 $M$ 行，每行包含：

kj Xj Yj

其中：

• $0\le k_j\le N$；
• $k_j=0$ 表示第 $j$ 条线段不使用移动步道；
• $k_j=i$ 表示第 $j$ 条线段沿第 $i$ 条移动步道行进；
• $(X_j,Y_j)$ 是第 $j$ 条线段的终点坐标。

所有实数至少输出小数点后六位。

样例输入

2
-100 -100 200 100 2.92893219 7.07106781
0 0 1 0 0 0
2000 0 2000 1 0 0

样例输出

50.000000
3
0 0.000000 0.000000
1 100.000000 0.000000
0 200.000000 100.000000

数据范围与限制

• $0\le N\le 50$
• 路线段数必须满足 $1\le M\le 300$
• 时间限制：$2\text{ s}$
• 空间限制：$64\text{ MB}$