符合条件的显然是两个球的交。设两点分别为 ，那么根据题意， 需要满足： 容易化为如下形式： 那么球心坐标就是： 半径就是：

将 看作是一段区间，那么考虑每次交换操作的贡献： 可以发现两区间无交集无论如何交换都满足其贡献 （事实上，如果令 ，那么 ），而有交集则 ，所以一定是尽量地选择有无集的区间交换。 引理： 时，「操作刚好 次」和「操作不超过 次」是等价的。 证明：将「操作不超过 次」的最优解执行完后，因为 ，根据鸽巢原理， 或者 的情况必然有一个的数量大于等于 ，那么反复交换这两个区间直到达到 次即可。 那么根据引理，将所有 和 分别从小到大、从大到小 sort 一遍，从前往后扫一遍，当后者大于前者时就将贡献加上，这样做能够使贡献最大化。 #include<iostream> #i...