team2012-D1-sol-0014

从 Trac 迁移的文章

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

原文章内容如下：

=== 题目大意 ===
在一个三维立方体 ((0,0,0) -> (10000,10000,10000)) 内有 n 组球体, 你需要从每组球体中选取一个(不能不选), 使得被选中的任意两个球都不会相交. 求最大的半径 R 使得存在合法的方案.

=== 数据范围 ===
 * 2 <= n <= 200

=== 解题思路 ===
二分半径 R, 验证是否有合法的方案. 裸的 2-SAT 问题, 而且这题还不用输出方案, 按照 2-SAT 算法搞, 不再赘述.

题目大意

在一个三维立方体 ((0,0,0) -> (10000,10000,10000)) 内有 n 组球体, 你需要从每组球体中选取一个(不能不选), 使得被选中的任意两个球都不会相交. 求最大的半径 R 使得存在合法的方案.

数据范围

• 2 <= n <= 200

解题思路

二分半径 R, 验证是否有合法的方案. 裸的 2-SAT 问题, 而且这题还不用输出方案, 按照 2-SAT 算法搞, 不再赘述.