P14189 [ICPC 2024 Hangzhou R] Catch the Star

BaoBao bought a telescope to observe a star in the night sky. The star is represented as a convex polygon $S$. However, there are $n$ convex polygonal moons $M_i$ that could obstruct his view. BaoBao can place his telescope anywhere on the $x$-axis between points $(l,0)$ and $(r,0)$, but he $\textbf{cannot}$ place it exactly at $(l,0)$ or $(r,0)$. Your task is to help BaoBao find the total length of the segments on the x-axis where he can position his telescope such that he has an unobstructed view of the star $S$, and whether he $\textbf{can}$ find a position at all. An unobstructed view means that no line segment from the chosen point on the x-axis to any point inside or on $S$ properly intersects any of the moons $M_i$. The line segment is allowed to touch the boundary of the moons but not cross through them.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \leq T \leq 2.5 \times 10^4$) indicating the number of test cases. For each test case: The first line contains three integers $n$, $l$, and $r$ ($1 \leq n \leq 10^4$, $-10^9 \leq l < r \leq 10^9$), denoting the number of moons and the range for telescope placement. The second line describes the star $S$ and begins with an integer $k_0$ ($3 \leq k_0 \leq 10^5$), denoting the number of vertices of $S$, followed by $2 \times k_0$ integers $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$), where $(x_{0,j},y_{0,j})$ is the coordinate of the $j$-th vertex of $S$ in counter-clockwise order. For the following $n$ lines, the $i$-th line describe moon $M_i$. Each line begins with an integer $k_i$ ($3 \leq k_i \leq 10^5$), denoting the number of vertices of $M_i$, followed by $2 \times k_i$ integers $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$), where $(x_{i,j},y_{i,j})$ is the coordinate of the $j$-th vertex of $M_i$ in counter-clockwise order. It is guaranteed that $S$ and $M_i$ are convex polygons. The star $S$, the moons $M_i$, and the segment from $(l,0)$ to $(r,0)$ do not touch or intersect with each other. However, different moons $M_i$ can intersect with each other. No three consecutive vertices of the same polygon are collinear. It's guaranteed that the sum of $\sum\limits_{i=0}^n k_i$ of all test cases does not exceed $10^6$. It is also guaranteed that the total number of polygons of all test cases (which is $\sum (n + 1)$) does not exceed $5 \times 10^4$.

For each test case, output a single line containing the total length of valid segments on the x-axis, strictly between $(l,0)$ and $(r,0)$, where BaoBao can place his telescope to see $S$ without obstruction. If there's no valid point between $(l,0)$ and $(r,0)$, output $-1$ instead. Your answer would be considered correct if the relative or absolute error does not exceed $10^{-9}$.

For the first sample, the first test case is illustrated below; the telescope can be located between $(-7,0)$ and $(-\frac{2}{3},0)$, or $(\frac{7}{2},0)$ and $(\frac{46}{7},0)$. :::align{center}  ::: The second test case is illustrated below; the telescope can be located between $(-8,0)$ and $(-2,0)$. :::align{center}  ::: Note that the input format in the third sample is for presentation purposes only, because we cannot print all the coordinates in one line without exceeding the width of the paper. Please refer to the other samples for more accurate input formatting.