BZPRO

#5328. [Sdoi2018]物理实验

内存限制：512 MiB 时间限制：30 Sec
提交 提交记录 讨论

题目描述

小T这学期有物理实验课，为了顺利完成下一节课的实验，他打算在课前对实验内容进行预习。这次实验在一个二
维平面上进行，平面上放置了一条无限长的直线导轨，导轨上放置了一个长为L的激光发射器，激光发射器会向导
轨两侧沿导轨垂直方向同时发射宽度为L的平行激光束。平面上还放置了n个挡板，每个挡板可以看作是一条线段，
现在每个挡板都不和直线导轨接触，且和直线导轨的夹角不超过85度，任意两个挡板也不会相互接触，激光束不能
穿透这些挡板，并且会被挡板吸收掉，不会被挡板反射出去。
小T想确定一个激光发射器的位置使得被激光束照射到的挡板长度之和最大，你需要帮小T算出这个最大值

输入格式

第一行包含一个正整数T，表示测试数据的组数，对于每组测试数据，
第一行是一个整数n，表示挡板个数，
接下来n行，每行包含四个整数x1,y1,x2,y2，表示挡板的两端点分别是(x1,y1)和(x2,y2)，保证(x1,y1)!=(x2,y2)，
第n+2行是五个整数x1,y1,x2,y2,L，表示直线导轨经过了点(x1,y1)和(x2,y2)，且激光发射器的长度为L，同样保证(x1,y1)!=(x2,y2)。
T <= 100，
1 <= n <= 10^4，
1 <= L <= 2*10^9，
所有坐标的绝对值不超过 10^9

输出格式

对于每组测试数据，输出一行，包含一个实数，表示激光束能照射到的挡板长度之和的最大值，要求相对误差不超过10^-6，
也就是说，令输出结果为a，标准答案为b，若满足|a-b|/max(1,b)<=10^-6，则输出结果会被认为是正确答案。

样例

样例输入


			
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

样例输出


			
3.000000000000000

3.118033988749895

4.251303782246768

数据范围与提示

请不要提交，尚无SPJ！


BZPRO Powered by Remmina.
Github Repository