题解 P14189【[ICPC 2024 Hangzhou R] Catch the Star】
Diaоsi
·
·
题解
Catch the Star
\color{gold}{\textsf{Medium-Hard}}
给定 n 个凸形障碍 M_i 和一个目标多边形 S，求出线段 \overline{(l,0)\,(r,0)} 上能够完整看到 S 的位置的长度。
对于每个障碍 M_i 求出它与 S 的两条内切线 m_1s_1, m_2s_2，不失一般性令 m_1\rightsquigarrow m_2 表示 M_i 上逆时针的一段弧，并且这段弧被夹在两条内切线中间。
那么 \overrightarrow{m_1s_1}, \overrightarrow{m_1m_2},\overrightarrow{s_2m_2} 的左开半平面交就是无法完整看到 S 的区域。把三个半平面分别与 \overline{(l,0)\,(r,0)} 求交，再把三个区间求交得到一个开区间 I_i。\bigcup_{i\in [n]} I_i 就是无法完全看到 S 的位置，取个补就能得到答案。
注意由于遮挡的位置是开区间，因此可能能够完整看到 S 的长度为 0 但是不为空（i.e., 有一些特定位置能够完整看到 S）。故求区间的部分需要有理数实现精确计算。
提交记录