zrj2012-B3-0014

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：给N组气球，每一组有两个气球，所有气球有固定的圆心。现在你可以从每组里选出一个气球，这N个气球必须有相同的半径，并且不能相交，每种选择都会有一个最大半径，求所有情况的最大半径。
如果我们确定了半径，能够判断这种情况是否有解，就可以二分答案。而如果半径确定了，题目就转化为一个2-sat的判定问题，具体做法可以去查询2-sat的做法。只要构图后去求强连通分量，如果同组的气球出现在同一个强连通分量中，就是无解。

题目大意：给N组气球，每一组有两个气球，所有气球有固定的圆心。现在你可以从每组里选出一个气球，这N个气球必须有相同的半径，并且不能相交，每种选择都会有一个最大半径，求所有情况的最大半径。

如果我们确定了半径，能够判断这种情况是否有解，就可以二分答案。而如果半径确定了，题目就转化为一个2-sat的判定问题，具体做法可以去查询2-sat的做法。只要构图后去求强连通分量，如果同组的气球出现在同一个强连通分量中，就是无解。