给出一个算法的n log n时间下界，以检查一组点是否具有特殊点k。
k定义为：
对于点的集合a，如果对于a中的每个点m，a中都有一个点q，使得k位于线段mq的中间，那么k不必属于a。
例如，对于四个点(1,0(、(0,1(、(1,1(、(0,0(的集合，该集合具有一个特殊点k=(0.5，0.5(。
当他们问我这个问题时，我完全是板着脸，什么也没想到。我想它需要一些强烈的几何背景。
O(nlogn)解决方案(我仍然不清楚你为什么要寻找下界解决方案。你还不如做一个详尽的检查，然后运行nlogn循环来确定下界。不是很难。我想你一定是指上界(：
通过对所有点求平均值，找到唯一有效的候选点。即求和它们的坐标并除以点数。如果这样的k存在，这就是它。如果不存在这样的k，我们会发现在最后一步中找到的点是无效的。
创建一个新的点阵列(集合(，在这里我们移动轴，使它们以点k为中心。即，如果k=(xk，yk+(，则点(x，y(将变为(x-xk，y-yk+/sub>(。根据比值x/y和范数sqrt(x2+y2(对点进行排序。正如下一步所示，如何进行这种排序并不重要，即哪个是主要标准，哪个是次要标准。
我们可以搜索每个点的补码，或者更好的方法是，简单地遍历数组并验证每两个相邻点确实是补码。也就是说，如果这是一个解，那么这个新数组中的每两个互补点都是(x，y(和(-x，-y(的形式，因为我们重新对中了轴，这意味着它们具有相同的比率("梯度"(和范数，并且在排序之后，必须是相邻的。
如果k是无效的，那么我们将在遍历中到达一个点，并发现它的邻居不是正确的/互补的形式===>没有这样的k。
时间=
用于查找候选k+
的O(n)O(n)用于构建新阵列，因为每个新点都可以在O(1(+
中计算排序的O(nlogn)+O(n)用于验证遍历
=O(nlogn)
我想说，你只需要计算质心(先去除重复项(，然后检查它是否是你的k。可能唯一导致它成为O(n log n)的事情就是在指定位置搜索一个点。