测试数据来自 system/2046

描述

小 T 这学期有物理实验课，为了顺利完成下一节课的实验，他打算在课前对实验内容进行预习。

这次实验在一个二维平面上进行，平面上放置了一条无限长的直线导轨，导轨上放置了一个长为 \(L\) 的激光发射器，激光发射器会向导轨两侧沿导轨垂直方向同时发射宽度为 \(L\) 的平行激光束。

平面上还放置了 \(n\) 个挡板，每个挡板可以看作是一条线段，现在每个挡板都不和直线导轨接触，且和直线导轨的夹角不超过 \(85^{\circ}\)，任意两个挡板也不会相互接触，激光束不能穿透这些挡板，并且会被挡板吸收掉，不会被挡板反射出去。

小 T 想确定一个激光发射器的位置使得被激光束照射到的挡板长度之和最大，你需要帮小 T 算出这个最大值。

格式

输入格式

第一行包含一个正整数 \(T\)，表示测试数据的组数，

对于每组测试数据，

第一行是一个整数 \(n\)，表示挡板个数，

接下来 \(n\) 行，每行包含四个整数 \(x_1,y_1,x_2,y_2\)，表示挡板的两端点分别是 \((x_1,y_1)\) 和 \((x_2,y_2)\)，保证 \((x_1,y_1) \neq (x_2,y_2)\)，

第 \(n+2\) 行是五个整数 \(x_1,y_1,x_2,y_2,L\)，表示直线导轨经过了点 \((x_1,y_1)\) 和 \((x_2,y_2)\)，且激光发射器的长度为 \(L\)，同样保证 \((x_1,y_1) \neq (x_2,y_2)\)。

输出格式

对于每组测试数据，输出一行，包含一个实数，表示激光束能照射到的挡板长度之和的最大值，四舍五入保留到小数点后3位。

样例1

样例输入1

3
4
-3 2 -1 2
-1 -1 1 -1
0 1 2 1
2 -2 4 -2
0 0 1 0 2
4
1 1 3 3
2 1 4 2
3 1 5 1
3 -1 4 -1
0 0 -1 0 2
4
-2 0 1 2
1 3 -3 2
1 -3 5 -1
2 -1 4 3
0 0 1 1 2

样例输出1

3.000
3.118
4.251

限制

• \(T \leq 100\)，
• \(1 \leq n \leq 10^4\)，
• \(1 \leq L \leq 2 \times 10^9\)，
• 所有坐标的绝对值不超过 \(10^9\)。

子任务1（40分）：满足 \(1\le n\le 100\) 且所有坐标的绝对值不超过 \(10^4\)。

子任务2（40分）：所有坐标的绝对值不超过 \(10^6\)。

子任务3（20分）：没有任何附加的限制。

来源

SDOI 2018 Round2