Description

BaoBao 买了一台望远镜，打算用它观测夜空中的一颗恒星。该恒星被表示为一个凸多边形 $S$。然而，有 $n$ 个凸多边形形状的“月亮” $M_i$ 可能会遮挡视线。BaoBao 可以将望远镜放置在 $x$ 轴上的任意位置，区间为 $(l,0)$ 到 $(r,0)$，但$\textbf{不能}$恰好放在 $(l,0)$ 或 $(r,0)$ 这两点上。

你的任务是帮助 BaoBao 计算出在 $x$ 轴上的哪些线段上可以放置望远镜，以便能够不被任何“月亮”遮挡地看到恒星 $S$，以及他是否有可能找到这样的放置位置。不被遮挡意味着，从选定的 $x$ 轴上的点发出的所有射线（即线段）指向 $S$ 内部或边界上的任意点，都不会与任何 $M_i$ 的内部部分严格相交。射线可以接触月亮的边界，但不能穿过其内部。

Input Format

有多组测试数据。输入的第一行为一个整数 $T$（$1 \leq T \leq 2.5 \times 10^4$），表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $n, l, r$（$1 \leq n \leq 10^4$，$-10^9 \leq l < r \leq 10^9$），表示月亮的数量以及望远镜可以摆放的区间范围。

第二行为恒星 $S$ 的描述，首先是一个整数 $k_0$（$3 \leq k_0 \leq 10^5$），表示 $S$ 的顶点数，接下来是 $2 \times k_0$ 个整数 $x_{0,1},y_{0,1},x_{0,2},y_{0,2},\cdots,x_{0,k_0},y_{0,k_0}$（$-10^9 \leq x_{0,j},y_{0,j} \leq 10^9$），其中 $(x_{0,j},y_{0,j})$ 是 $S$ 的第 $j$ 个顶点，按逆时针顺序给出。

接下来的 $n$ 行，每行描述一个月亮 $M_i$。每行首先是一个整数 $k_i$（$3 \leq k_i \leq 10^5$），表示 $M_i$ 的顶点数，之后是 $2 \times k_i$ 个整数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2},\cdots,x_{i,k_i},y_{i,k_i}$（$-10^9 \leq x_{i,j},y_{i,j} \leq 10^9$），其中 $(x_{i,j},y_{i,j})$ 是 $M_i$ 的第 $j$ 个顶点，按逆时针顺序给出。

保证 $S$ 和所有 $M_i$ 都是凸多边形。恒星 $S$、所有月亮 $M_i$、以及区间 $(l,0)$ 到 $(r,0)$ 对应的线段两端彼此互不接触也不相交。但不同的 $M_i$ 之间可以相交。任意多边形自身不会有三点共线。

保证所有测试数据中 $\sum\limits_{i=0}^n k_i$ 的总和不超过 $10^6$。测试数据中所有多边形的总数 $\sum (n + 1)$ 不超过 $5 \times 10^4$。

Output Format

对于每组测试数据，输出一行，表示在 $(l,0)$ 与 $(r,0)$ 之间，可以合法放置望远镜的区间总长度（可以保留小数），如果不存在任何合法位置，则输出 $-1$。

当你的答案的相对或绝对误差不超过 $10^{-9}$ 时，将被视为正确。

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

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

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

Hint

对于第一个样例，第一组测试数据如图所示，望远镜可以放在 $(-7,0)$ 到 $(-\frac{2}{3},0)$，或者 $(\frac{7}{2},0)$ 到 $(\frac{46}{7},0)$ 之间。

:::align{center} :::

第二组测试数据如图所示，望远镜可以放在 $(-8,0)$ 到 $(-2,0)$ 之间。

:::align{center} :::

注意，第三组样例中的输入格式仅为便于展示，因为无法在一行内展示全部坐标。请参考其他样例以获得更精确的输入格式。

由 ChatGPT 5 翻译