题解 P17213【[ICPC 2017 Nanning R] The Ball】
Diaоsi
·
·
题解
The Ball
\color{cornflowerblue}{\textsf{Medium}}
给出 n 个半空间 a_ix+b_iy+c_iz\leq d_i 和 \{x\geq 0,y\geq 0,z\geq 0\}，求出半空间交内能够放下的最大的球。
1\leq n\leq 100.
把 \{x\geq 0,y\geq 0,z\geq 0\} 当成一般半空间处理即可，对于半空间 a_ix+b_iy+c_iz\leq d_i，其法向量为 n_i=(a_i,b_i,c_i)；假设球心为 c=(x,y,z)，球中的点满足 \|p-c\|\leq r，而一个半空间只会对球上的唯一一个点 p=c+r\cdot(n_i/\|n_i\|) 产生最强的限制，因此只需要使得这个点在圆内。
问题被转化成：
\begin{aligned}
&\max r \\
&\text{s.t.} \quad a_ix+b_iy+c_iz + r\sqrt{a_i^2+b_i^2+c_i^2}\leq d_i,\quad i=1,\dots,n
\end{aligned}
使用单纯形法求解可以通过，也可以使用随机增量法做到 \mathcal{O}(n)。