这题 wqs 二分做法是假的吧？？？

如题，在第一篇 wqs 二分做法（@ xryjr233）中有一个三方暴力，但在这组数据上他的正解和暴力的相对/绝对误差都超过了题目要求的

10^{-4}

：

CPP

11 4 4
0.587 0.828 0.182 0.968 0.324 0.825 0.969 0.048 0.439 0.401 0.541
0.235 0.749 0.116 0.686 0.275 0.192 0.145 0.404 0.066 0.873 0.261

CPP

5.6500000000

但他输出了 5.75200。

由于这组数据 @ Dementor 的题解过得去，我便怀疑可能是他写挂了，但没过多久，我又找到了一组数据：

CPP

24 12 7
0.2 0.5 0.8 0.9 0.2 0.6 0.4 0.5 0.1 0.7 0.8 0.0 0.1 1.0 0.7 0.3 0.6 0.9 0.3 0.2 0.2 0.6 0.2 0.3
0.8 0.5 0.8 0.9 0.2 0.1 0.1 0.3 0.8 0.7 0.7 0.9 0.3 0.8 0.4 0.4 0.4 0.6 0.9 0.7 0.3 0.3 0.9 0.2

CPP

14.0000000000

而他输出了 14.037499992549，这里的相对误差约为 0.0027。

同时，第一组数据还 Hack 掉了 @ wrpwrp 的最后一份代码等，第二组数据还 Hack 掉了 @ BlankAo 的代码等。

为什么说本题中 wqs 二分做法是假的？首先，没有题解明确给出凸性的理性证明（只有感性理解），那么你可以去看看这题，看似具有凸性实则不然（见第二个样例）；其次，就算你证明了它是凸的，那你也只能用一层 wqs 二分，因为如果存在两种方案，两种球要用的个数不同，但期望抓住的总个数相同，那你选哪一种呢？这就是这些题解假的原因，而由于我这么菜所以目前也没想出什么较好的解决方案。

所以这题是不是只有

O(n^2\log n)

的做法了啊，感觉

O(n\log^2n)

突然变成了

O(n^2\log n)

又有些不甘心，但又没法证明它是对的。所以有没有大佬来指点指点。！

最后附一组在题解区翻到的更小但更强的数据。

CPP

3 1 1 
1 1 1
1 1 1

CPP

这题 wqs 二分做法是假的吧？？？

讨论操作

回复

相关推荐

这题 wqs 二分做法是假的吧？？？