用于测试使用列表中的任意两个点构建的每个矩形是否包含该列表中的第三个点的快速算法
Fast algorithm for testing if every rectangle built using any two points from a list contains a third point from that list
问题如下：
给定 N (N <= 100,000) 个点的笛卡尔坐标，测试使用其中任意两个构建的每个矩形（面积 > 0）是否至少包含矩形内部或外部列表中的另一个点他的保证金。
我知道 O(N^2) 时间复杂度的算法。我想找到 O(N * logN) 的解决方案。内存不是问题。
当我说两个点定义一个矩形时，我的意思是这两个点位于矩形的两个对角。矩形的边平行于笛卡尔轴。
这里有两个例子：
N = 4
Points:
1 1
3 5
2 4
8 8
不正确:（矩形 (1, 1) - (2, 4) 内部或边缘没有任何点）。
N = 3
Points:
10 9
13 9
10 8
正确。
按照坐标对的 max 从低到高 (O(n*log(n))) 对点进行排序。从左下点（最低最大坐标）开始，如果顺序中的下一个点 不共享 原始点的 x 值或其 y 值（例如 (1,2) 和 (5,2) 共享 2 的 y 坐标，但 (1,2) 和 (2, 1) 没有共同的坐标），点集未通过测试.否则，移动到下一个点。如果这样到达终点（O(n)），则集合有效。整个算法是O(n*log(n)).
说明
共享坐标值的两个点位于平行于其中一个轴的直线上，因此它们之间没有绘制矩形（因为这样的矩形的面积 = 0）。
对于给定点 p1，如果顺序中的下一个 "bigger" 点 p2 直接垂直或从 p1 水平（即共享一个坐标值），然后所有指向 p2 右上角的点与 形成矩形p1 包含 p2，因此集合中没有矩形以 p1 作为左下角并且缺少一个内点。
但是，如果下一个更大的点是 p2 的对角线，则 p1 <-> p2 矩形内部没有集合中的点，所以集合无效。
对于集合中的每个点 P = (a, b)，搜索形式为 Y = (x, b) 和 X = (a, y) 的最近点，使得 x > a 和 y > b。
然后，求X, Y两点定义的矩形是否包含*内点R[=17] =]、X 和 Y。如果是这样，很容易看出矩形 P, R 不包含集合中的任何其他点。
如果集合中不存在符合 X 或 Y 限制的点，则必须分别使用 (a, ∞) 或 (∞, b)。
该算法的计算成本为 O(NlogN):
可以在预排序列表 [O(NlogN)] 上使用二分查找 [O(logN)] 来查找 X 或 Y。
可以使用一些空间树结构作为四叉树或 k-d 树 [O(logN)].
*) 如果X, Y包含多个内部点，则应选择R作为最接近P的。
更新：上述算法适用于由左下角和右上角定义的矩形。为了使其也适用于由其右下角和左上角定义的矩形，一个新点 X' （这样它最接近 X' = (a, y') 形式的 P 其中 y' < b) 和由 X', Y 定义的相应矩形也应该考虑到集合中的每个点。
问题如下：
给定 N (N <= 100,000) 个点的笛卡尔坐标，测试使用其中任意两个构建的每个矩形（面积 > 0）是否至少包含矩形内部或外部列表中的另一个点他的保证金。
我知道 O(N^2) 时间复杂度的算法。我想找到 O(N * logN) 的解决方案。内存不是问题。
当我说两个点定义一个矩形时，我的意思是这两个点位于矩形的两个对角。矩形的边平行于笛卡尔轴。
这里有两个例子：
N = 4
Points:
1 1
3 5
2 4
8 8
不正确:（矩形 (1, 1) - (2, 4) 内部或边缘没有任何点）。
N = 3
Points:
10 9
13 9
10 8
正确。
按照坐标对的 max 从低到高 (O(n*log(n))) 对点进行排序。从左下点（最低最大坐标）开始，如果顺序中的下一个点 不共享 原始点的 x 值或其 y 值（例如 (1,2) 和 (5,2) 共享 2 的 y 坐标，但 (1,2) 和 (2, 1) 没有共同的坐标），点集未通过测试.否则，移动到下一个点。如果这样到达终点（O(n)），则集合有效。整个算法是O(n*log(n)).
说明
共享坐标值的两个点位于平行于其中一个轴的直线上，因此它们之间没有绘制矩形（因为这样的矩形的面积 = 0）。
对于给定点 p1，如果顺序中的下一个 "bigger" 点 p2 直接垂直或从 p1 水平（即共享一个坐标值），然后所有指向 p2 右上角的点与 形成矩形p1 包含 p2，因此集合中没有矩形以 p1 作为左下角并且缺少一个内点。
但是，如果下一个更大的点是 p2 的对角线，则 p1 <-> p2 矩形内部没有集合中的点，所以集合无效。
对于集合中的每个点 P = (a, b)，搜索形式为 Y = (x, b) 和 X = (a, y) 的最近点，使得 x > a 和 y > b。
然后，求X, Y两点定义的矩形是否包含*内点R[=17] =]、。如果是这样，很容易看出矩形 X 和 YP, R 不包含集合中的任何其他点。
如果集合中不存在符合 X 或 Y 限制的点，则必须分别使用 (a, ∞) 或 (∞, b)。
该算法的计算成本为 O(NlogN):
可以在预排序列表 [O(NlogN)] 上使用二分查找 [O(logN)] 来查找
X或Y。可以使用一些空间树结构作为四叉树或 k-d 树 [O(logN)].
来寻找 R
*) 如果X, Y包含多个内部点，则应选择R作为最接近P的。
更新：上述算法适用于由左下角和右上角定义的矩形。为了使其也适用于由其右下角和左上角定义的矩形，一个新点 X' （这样它最接近 X' = (a, y') 形式的 P 其中 y' < b) 和由 X', Y 定义的相应矩形也应该考虑到集合中的每个点。