#P2074. Line of Sight
Line of Sight
题目翻译
一位建筑师对他的新房子非常自豪,并希望确保路过他房产边界(沿街道)的人们能够看到它。房产内有各种树木、灌木、树篱和其他可能遮挡视线的障碍物。为了简化问题,我们将房屋、房产边界和障碍物建模为与轴平行的直线:
为了满足建筑师的需求,你需要编写一个程序,输入房屋、房产边界和周围障碍物的位置,并计算房产边界上能够完整看到房屋的最长连续部分的长度(即没有任何部分被障碍物遮挡)。
输入格式
每个对象(房屋、房产边界、障碍物)用一行表示,包含左坐标、右坐标和坐标: <> <> <> 其中 、 和 是非负实数,且 < 。
输入文件可以描述多个房屋的场景。对于每个房屋:
第一行是房屋的坐标。
第二行是房产边界的坐标。
第三行是一个整数,表示障碍物的数量。
接下来的若干行是每个障碍物的坐标,每行一个。
输入以 结束。
对于每个房屋,房屋位于房产边界的上方(即 > )。障碍物不会与房屋或房产边界重叠(例如,如果障碍物的 y 与房屋的 y 相同,则障碍物的 [, ] 不会与房屋的 [, ] 相交)。
输出格式
对于每个房屋,输出房产边界上能够完整看到房屋的最长连续线段的长度,保留两位小数。如果没有这样的线段,输出 " "。
输入数据 1
2 6 6
0 15 0
3
1 2 1
3 4 1
12 13 1
1 5 5
0 10 0
1
0 15 1
0 0 0
输出数据 1
8.80
No View