zrj2012-B3-0004

从 Trac 迁移的文章

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

原文章内容如下：

题目大意：给出四个顶点作为圆心，要求给这些圆分配半径，使得4个圆相互没有公共部分，在这个前提下，求4个半径和的最大值。

这道题MS原本是线性规划题，记第i个圆的半径是ri，则对任意i!=j，需要满足
0<=ri+rj<=distance(i,j)。MS原本出题人是希望我们这么做得，据说218有上将模板，可过此题。

不过MS约束条件和题目的特殊性，只需要将4个顶点分成2组(a1,a2)与(b1,b2)，min(distance(a1,a2)+distance(b1,b2))就是答案。

具体为什么，求数学帝指点。

题目大意：给出四个顶点作为圆心，要求给这些圆分配半径，使得4个圆相互没有公共部分，在这个前提下，求4个半径和的最大值。

这道题MS原本是线性规划题，记第i个圆的半径是ri，则对任意i!=j，需要满足

0<=ri+rj<=distance(i,j)。MS原本出题人是希望我们这么做得，据说218有上将模板，可过此题。

不过MS约束条件和题目的特殊性，只需要将4个顶点分成2组(a1,a2)与(b1,b2)，min(distance(a1,a2)+distance(b1,b2))就是答案。

具体为什么，求数学帝指点。