问题描述

有一种打印机，通过发射激光在 $xy$ 平面上打印线段。

在打印开始时，激光位置在坐标 $(0,0)$ 处。

打印线段时，请遵循以下步骤。

• 首先，将激光位置移动到线段的一个端点。
  • 可以从任一端点开始绘制。
• 然后，在发射激光的同时，将激光位置从当前端点沿直线移动到另一个端点。
  • 不允许在线段中间停止打印。
• 当不发射激光时，激光位置可以以每秒 $S$ 个单位的速度向任何方向移动。
• 当发射激光时，激光位置可以以每秒 $T$ 个单位的速度沿着正在打印的线段移动。
• 移动激光位置以外的操作所需的时间可以忽略不计。

高桥想用这台打印机打印 $N$ 条线段。

第 $i$ 条线段连接坐标 $(A_i,B_i)$ 和 $(C_i,D_i)$。

一些线段可能会重叠，在这种情况下，他需要分别打印每个线段的重叠部分。

当他以最佳方式操作印刷机时，完成所有线段的印刷所需的最小秒数是多少？

数据规模

所有输入值都是整数。

$1\le N\le 6$

$1\le T\le S\le 1000$

$-1000\le A_i,B_i,C_i,D_i\le 1000$

$(A_i,B_i)\neq(C_i,D_i)(1\le i\le N)$

输入

输入来自标准输入，格式如下:

$N\ S\ T$

$A_1\ B_1\ C_1\ D_1$

$\vdots$

$A_N\ B_N\ C_N\ D_N$

输出

打印答案。

答案的绝对误差或者相对误差不超过 $10^{-6}$ 即认为正确。

3 2 1
1 3 2 1
0 2 0 0
3 0 2 0

6.44317475868633722080

• 发射激光，同时将激光位置从 $(0,0)$ 移动到 $(0,2)$，打印第二条线段。
  • 这需要 $2$ 秒钟。
• 将激光位置从 $(0,2)$ 移动到 $(1，3)$，但不发射激光。
  • 这需要 $\sqrt{2}/2$ 秒。
• 发射激光，同时将激光位置从 $(1,3)$ 移动到 $(2,1)$ ，打印第一条线段。
  • 这需要$\sqrt{5}$ 秒。
• 将激光位置从 $(2,1)$ 移动到 $(2,0)$ ，但不发射激光。
  • 这需要 $1/2$ 秒。
• 发射激光，同时将激光位置从 $(2,0)$ 移动到 $(3,0)$，打印第三条线段。
  • 这需要 $1$ 秒钟。
• 总时间为 $2+(\sqrt{2}/2)+\sqrt{5}+(1/2)+1≈6.443175$ 秒。

2 1 1
0 0 10 10
0 2 2 0

20.97056274847714058517

6 3 2
-1000 -1000 1000 1000
1000 -1000 -1000 1000
-1000 -1000 1000 1000
1000 -1000 -1000 1000
1000 1000 -1000 -1000
-1000 1000 1000 -1000

9623.35256169626864153344

这里有多条线段重叠，需要分别为每条线段打印重叠部分。

6 10 8
1000 1000 -1000 -1000
1000 -1000 -1000 -1000
-1000 1000 1000 1000
-1000 1000 -1000 -1000
1000 1000 1000 -1000
1000 -1000 -1000 1000

2048.52813742385702910909