所以问题如下：给定数据库中的 N 个点（编辑：暂时假设它是 2 个数组 x[] 和 y[]），每个数组都有坐标(x[i], y[i])，查询格式(X,Y,R)，列出圆中的所有点 center (X,Y)，半径R。
编辑 - 输入约束： x=[-180,180], y=[-180,180]
哪个 Python 库可以最快的方式解决这个问题？我正在寻找O(log(N) + K)每个查询的时间复杂度和<= O(n * log(N)^2)空间要求，K输出长度在哪里。
解决方案0： 循环N个点，用毕达哥拉斯检查。
- >内存：O(N)。每次查询的时间：O(N)
解决方案 0.1：
与上面相同，但添加了一些小东西，例如按 排序x，并使用二进制搜索开始仅搜索坐标为 的点x[i] >= X - R。使用平方距离而不是距离等
-> 每次查询的时间：仍然O(N)但更快
解决方案 1四叉树。假设点以 (0,0) 为中心。树的根节点在 (0,0)，包含 2D 空间(x=[-inf,inf],y=[-inf,inf])。每个节点有 4 个孩子：每个孩子包含父亲的 1/4 象限。因此，每当我们降低一个级别时，搜索空间就会减少 75%。继续往下走，直到当前节点在查询圈之外，或者不包含数据点。-> 记忆：也许O(n * log(N)^2)？， 时间：~~O(log(N)^2)
他们的任何 python 库是否已经解决了这个问题？