#P18265. Catch the Star

Catch the Star

Catch the Star

题目描述

BaoBao 买了一台望远镜,准备观察夜空中的一颗星星。星星用凸多边形 SS 表示,但还有 nn 个用凸多边形 MiM_i 表示的月亮,可能遮挡视线。

BaoBao 可以把望远镜放在 xx 轴上 (l,0)(l,0) 与 (r,0)(r,0) 之间的任意位置,但不能恰好放在这两个端点。

请你求出所有能够完整、无遮挡地看到星星 SS 的合法位置组成的线段的总长度,并判断是否至少存在一个合法位置。

这里,观察点 PP 能无遮挡地看到 SS,是指从 PP 到 SS 内部或边界上任意一点的线段,都不穿过任何月亮 MiM_i 的内部。视线允许接触月亮的边界,但不能从月亮内部穿过。

注意:合法位置可能只有孤立的点。这时存在合法位置,但总长度为 00;它与完全没有合法位置的情况不同。

输入格式

第一行包含一个整数 TT(1≤T≤250001\le T\le25000),表示测试用例数量。每个测试用例格式如下。

第一行包含三个整数 n,l,rn,l,r(1≤n≤1041\le n\le10^4,−109≤l<r≤109-10^9\le l<r\le10^9),分别表示月亮数量和望远镜允许放置的范围。

第二行描述星星 SS:首先给出顶点数 k0k_0(3≤k0≤1053\le k_0\le10^5),随后给出 2k02k_0 个整数

$$x_{0,1},y_{0,1},x_{0,2},y_{0,2},\ldots,x_{0,k_0},y_{0,k_0},$$

依次表示星星按逆时针顺序排列的顶点坐标。

接下来 nn 行,第 ii 行描述月亮 MiM_i:首先给出顶点数 kik_i(3≤ki≤1053\le k_i\le10^5),随后给出按逆时针顺序排列的 2ki2k_i 个顶点坐标。

所有坐标均为整数,满足 −109≤xi,j,yi,j≤109-10^9\le x_{i,j},y_{i,j}\le10^9。

输入保证:

  • SS 和所有 MiM_i 都是凸多边形,同一多边形的任意三个连续顶点不共线。
  • 星星 SS、任意月亮 MiM_i、从 (l,0)(l,0) 到 (r,0)(r,0) 的线段,两两之间不接触也不相交。
  • 不同月亮之间可以接触、相交或重叠。
  • 所有测试用例的顶点总数 ∑∑i=0nki\sum\sum_{i=0}^{n} k_i 不超过 10610^6。
  • 所有测试用例的多边形总数 ∑(n+1)\sum(n+1) 不超过 5×1045\times10^4。

输出格式

对于每个测试用例,输出一行一个数,表示开线段 (l,0)(l,0) 到 (r,0)(r,0) 上所有合法位置的总长度。

如果其中不存在任何合法点,输出 −1-1。否则即使总长度为 00,也应输出 00。

答案的绝对误差或相对误差不超过 10−910^{-9} 即视为正确。

样例 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的第一个测试用例如下图所示:望远镜可以位于 (−7,0)(-7,0) 到 (−23,0)(-\frac23,0) 之间,或者 (72,0)(\frac72,0) 到 (467,0)(\frac{46}7,0) 之间。

样例1第一个测试用例的星星、月亮和视线

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

样例1第二个测试用例的星星、月亮和视线

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