2023-10-14
题目
题目描述
难度&重要性(1~10):7
题目来源
CQYC
题目算法
几何，二分
解题思路
Sol
我们知道，对于两个圆，我们无非就只有三种情况：相离，相切，相交。而这道题目是不允许其他圆相交，而两个圆不相交只有两种情况：包含，不包含。
根据垂径定理得知，过线段两端的圆的圆心是一定在线段的中垂线上的。而对于每一个其他的圆，与其相交的圆心一定是在一个连续的区间之间的。那么我们就可以考虑用二分来对每一个圆判断不能存在的区间，再将这一段区间打到一个数轴上，用扫描线来找最小半径就行了。
如图，我们就需要将 \(O'O''\) 打到一个数轴上，用扫描线找到最小半径就行了。
细节比较多，请看代码。