#P18265. Catch the Star
Catch the Star
Catch the Star
题目描述
BaoBao 买了一台望远镜,准备观察夜空中的一颗星星。星星用凸多边形 表示,但还有 个用凸多边形 表示的月亮,可能遮挡视线。
BaoBao 可以把望远镜放在 轴上 与 之间的任意位置,但不能恰好放在这两个端点。
请你求出所有能够完整、无遮挡地看到星星 的合法位置组成的线段的总长度,并判断是否至少存在一个合法位置。
这里,观察点 能无遮挡地看到 ,是指从 到 内部或边界上任意一点的线段,都不穿过任何月亮 的内部。视线允许接触月亮的边界,但不能从月亮内部穿过。
注意:合法位置可能只有孤立的点。这时存在合法位置,但总长度为 ;它与完全没有合法位置的情况不同。
输入格式
第一行包含一个整数 (),表示测试用例数量。每个测试用例格式如下。
第一行包含三个整数 (,),分别表示月亮数量和望远镜允许放置的范围。
第二行描述星星 :首先给出顶点数 (),随后给出 个整数
$$x_{0,1},y_{0,1},x_{0,2},y_{0,2},\ldots,x_{0,k_0},y_{0,k_0},$$依次表示星星按逆时针顺序排列的顶点坐标。
接下来 行,第 行描述月亮 :首先给出顶点数 (),随后给出按逆时针顺序排列的 个顶点坐标。
所有坐标均为整数,满足 。
输入保证:
- 和所有 都是凸多边形,同一多边形的任意三个连续顶点不共线。
- 星星 、任意月亮 、从 到 的线段,两两之间不接触也不相交。
- 不同月亮之间可以接触、相交或重叠。
- 所有测试用例的顶点总数 不超过 。
- 所有测试用例的多边形总数 不超过 。
输出格式
对于每个测试用例,输出一行一个数,表示开线段 到 上所有合法位置的总长度。
如果其中不存在任何合法点,输出 。否则即使总长度为 ,也应输出 。
答案的绝对误差或相对误差不超过 即视为正确。
样例 1
2
4 -8 8
3 -7 7 -6 8 -7 8
3 -9 -2 -7 3 -9 -1
3 -2 3 0 2 -4 5
3 5 1 5 3 4 2
3 1 -1 2 -2 3 -1
5 -8 8
5 -14 -3 -10 -2 -9 2 -10 4 -12 5
3 -16 0 -15 0 -15 1
3 -15 6 -9 5 -15 7
3 -10 5 -9 5 -10 6
3 -7 3 -3 2 -8 4
3 -6 -1 -6 -2 -5 -1
9.404761904761905
6.000000000000000
样例 2
3
1 -4 4
3 -2 6 0 5 2 6
3 -3 1 3 1 0 4
3 -2 2
3 -2 4 2 4 0 6
3 -2 2 -1 2 -2 3
3 1 2 2 2 2 3
3 -2 -1 0 -3 2 -1
1 1 2
3 -8 0 -7 0 -8 1
3 -5 0 -4 -1 -4 0
-1.000000000000000
0.000000000000000
1.000000000000000
样例 3
1
1 -744567334 955216804
5
-781518205 -852078097
-781516900 -852078384
-781516392 -852076569
-781518329 -852076047
-781519925 -852077600
5
-393011614 -131855702
-393010699 -131856607
-393008846 -131856475
-393009388 -131854587
-393010201 -131854694
1699779738.691979192313738
样例说明
样例1的第一个测试用例如下图所示:望远镜可以位于 到 之间,或者 到 之间。

样例1的第二个测试用例如下图所示:望远镜可以位于 到 之间。观察范围端点 和 始终不能使用,月亮边界可以被视线接触。

样例3把同一个多边形的坐标拆成多行,目的是避免排版超出纸张宽度。输入按空白字符分隔读取即可;通常输入格式请参考前两个样例。