P14189 [ICPC 2024 Hangzhou R] Catch the Star

BaoBao 买了一台望远镜，打算用它观测夜空中的一颗恒星。该恒星被表示为一个凸多边形 $S$。然而，有 $n$ 个凸多边形形状的“月亮” $M_i$ 可能会遮挡视线。BaoBao 可以将望远镜放置在 $x$ 轴上的任意位置，区间为 $(l,0)$ 到 $(r,0)$，但$\textbf{不能}$恰好放在 $(l,0)$ 或 $(r,0)$ 这两点上。 你的任务是帮助 BaoBao 计算出在 $x$ 轴上的哪些线段上可以放置望远镜，以便能够不被任何“月亮”遮挡地看到恒星 $S$，以及他是否有可能找到这样的放置位置。不被遮挡意味着，从选定的 $x$ 轴上的点发出的所有射线（即线段）指向 $S$ 内部或边界上的任意点，都不会与任何 $M_i$ 的内部部分严格相交。射线可以接触月亮的边界，但不能穿过其内部。

有多组测试数据。输入的第一行为一个整数 $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$。

对于每组测试数据，输出一行，表示在 $(l,0)$ 与 $(r,0)$ 之间，可以合法放置望远镜的区间总长度（可以保留小数），如果不存在任何合法位置，则输出 $-1$。 当你的答案的相对或绝对误差不超过 $10^{-9}$ 时，将被视为正确。

对于第一个样例，第一组测试数据如图所示，望远镜可以放在 $(-7,0)$ 到 $(-\frac{2}{3},0)$，或者 $(\frac{7}{2},0)$ 到 $(\frac{46}{7},0)$ 之间。 :::align{center}  ::: 第二组测试数据如图所示，望远镜可以放在 $(-8,0)$ 到 $(-2,0)$ 之间。 :::align{center}  ::: 注意，第三组样例中的输入格式仅为便于展示，因为无法在一行内展示全部坐标。请参考其他样例以获得更精确的输入格式。 由 ChatGPT 5 翻译