Comet OJ

C0696 [SDOI2018]物理实验

内存限制：512 MB 时间限制：10000 ms

题目描述

小 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)$。

输出

对于每组测试数据，输出一行，包含一个实数，表示激光束能照射到的挡板长度之和的最大值，要求相对误差不超过 $10^{-6}$，

也就是说，令输出结果为 $a$，标准答案为 $b$，若满足 $\frac{ \left | a-b \right | }{max(1,b)} \leq 10^{-6}$，则输出结果会被认为是正确答案。

样例

样例输入 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.000000000000000
3.118033988749895
4.251303782246768

提示

对于 $40\%$ 的数据，满足 $1\le n\le 100$ 且所有坐标的绝对值不超过 $10^4$。

对于另外 $40\%$ 的数据，所有坐标的绝对值不超过 $10^6$。

对于 $100\%$ 的数据，$T \leq 100 , 1 \leq n \leq 10^4 , 1 \leq L \leq 2 \times 10^9$，所有坐标的绝对值不超过 $10^9$。