CircusTents
作者：毛啸
关键词：二分答案 计算几何
题目简述
个实心圆，两两没有交集，在第一个圆上找一个点，使得它到另外一个圆上某个点的最短距离的最小值尽量大，两个点之间的最短距离是指连接两个点且中途不进入任何一个实心圆内部的路径的长度的最小值。
。
二分答案
很多“最小值尽量大”的题，基本思路都是二分答案，本题也不例外，可以二分答案并判断是否有一个点距离最小值不小于。
简化问题
考虑“连接两个点且中途不进入任何一个实心圆内部的路径的长度的最小值”，我们发现，不进入任何一个实心圆内部很难处理，但是我们发现，如果我们进入的实心圆不是第一个圆，由于我们要求的是距离的最小值，所以这个路径对我们已经没有意义了，所以我们完全可以把这个拗口的家伙改成 “连接两个点且中途不进入第一个实心圆内部的路径的长度的最小值”。
路径可能性
那么这条路径是怎么走的呢，显然只有两种可能：如果能直接走过去就直接走过去，否则一定是在圆上绕一段再直接走过去。并且区分这两种情况也非常简单，我们只要作出终点圆圆心关于起点圆的两条切线并连结切点形成一个三角形，如果在三角形内部则直接走过去，否则就绕到最近的切点再沿切线走过去。
转化模型
我们发现，一个点走到一个圆距离是否超过的问题，可以转化成将圆的半径扩大之后，这个点是否在圆内的问题。
所以问题就很简单了，假设二分的值是，那么我们将所有圆半径都扩大。然后对于路径的两种情况我们可以逐个击破。
如果扩大之后的圆包含了第一个圆显然就无解了，如果两个圆相离或者两个圆相交且交点都在前面提到的切线形成的三角形中（显然由于两个交点和两条都关于连结两个圆形的直线轴对称，因此它们要么都在三角形内，要么都在三角形外），那么对应的路径是直接走过去，这就对应着一段圆上的一段角度区间不可行。
否则，对应的路径是绕着圆走完之后走切线，由于切线长度确定，因此，我们可以直接算出对应的可行角度区间。
所以，问题成了一堆角度区间不可行，问不可行角度区间的并是否是全集。
如果是线段上那么用简单的区间并即可解决。
如果是圆上，我们可以将跨过零度的区间分成两部分，转化成线段上的情况。问题完美解决。
时间复杂度，空间复杂度，其中是二分次数。