#P2074. Line of Sight

Line of Sight

题目翻译

一位建筑师对他的新房子非常自豪,并希望确保路过他房产边界(沿街道)的人们能够看到它。房产内有各种树木、灌木、树篱和其他可能遮挡视线的障碍物。为了简化问题,我们将房屋、房产边界和障碍物建模为与xx轴平行的直线:

为了满足建筑师的需求,你需要编写一个程序,输入房屋、房产边界和周围障碍物的位置,并计算房产边界上能够完整看到房屋的最长连续部分的长度(即没有任何部分被障碍物遮挡)。

输入格式

每个对象(房屋、房产边界、障碍物)用一行表示,包含左xx坐标、右xx坐标和yy坐标: <x1x1> <x2x2> <yy> 其中 x1x1x2x2yy 是非负实数,且 x1x1 < x2x2

输入文件可以描述多个房屋的场景。对于每个房屋:

第一行是房屋的坐标。

第二行是房产边界的坐标。

第三行是一个整数,表示障碍物的数量。

接下来的若干行是每个障碍物的坐标,每行一个。

输入以 00 00 00 结束。

对于每个房屋,房屋位于房产边界的上方(即 house.yhouse.y > propertyline.yproperty_line.y)。障碍物不会与房屋或房产边界重叠(例如,如果障碍物的 y 与房屋的 y 相同,则障碍物的 [x1x1, x2x2] 不会与房屋的 [x1x1, x2x2] 相交)。

输出格式

对于每个房屋,输出房产边界上能够完整看到房屋的最长连续线段的长度,保留两位小数。如果没有这样的线段,输出 "NoNo ViewView"。

输入数据 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