问分而治之，计算各点的秩

EN

使用任意nlogn排序algo(快速排序或合并排序)对给定的点进行排序。其中比较函数同时考虑了x和y。现在，由于我们已经对列表/数组进行了排序，我们可以对这个排序的数组执行二进制搜索，以找到输入点的位置。现在，我们有排序数组中的位置，这个位置下面的所有点都是我们所需要的。如果您使用数组作为您的数据结构，由于一次性性质，位置是您的答案。

时间复杂度:排序需要n* log n二进制搜索需要log n返回位置为0(1)。

共计=n* log n+ log n+1

与n* logn相比，(logn+ 1)只是一个常数，对于一个非常大的数据集来说，这个常数变得非常小。所以，您的总体复杂度仍然是n * log。

例如，假设数据点的数目是100。然后，100 * log (100) = 200。(以基数为10)。log (100 ) +(100* log(100)) = 202。

你看，额外的日志(N)使时间复杂度从200到202。因此，对于一个非常大的数据集，您可以安全地忽略将log(n)添加为一个常量。