algorithm - 不同三角形顶点的数量

Question

我被要求解决以下问题:

Consider you are given N distinct points with both a positive x coordinate and positive y coordinate. For each coordinate you are to form a right triangle with two sides that connect the coordinate and the x-axis 45 degrees relative to the x-axis. Thus a right angle is formed at the intersection of both sides, and the hypotenuse of the triangle is on the x-axis. After you have created these triangles, find number of points out of the given N points in which none of the created triangles overlap with these points.

For example, let's say N = 3 and we are given the points : (4, 6), (7, 2), (2, 5)

Additional vertices for triangle of point (4,6) : (-2,6), (10,6)

Additional Vertices for trianlge of point (7,2) : (5,2), (9,2)

Additional Vertices for triangle of point (2,5) : (-3,5), (7,5)

In this example the triangle formed by the coordinate (4,6) would overlap with the coordinate (7,2), thus the correct output would be 2 since only the points (4,6) and (2,5) do not overlap with any created triangles.

到目前为止，我已经观察到，为了检查一个点的三角形是否与 N 个点之一相交，您取 y 值的差值并检查它是否大于或等于x 值，因为三角形边的斜率始终为 1。使用此属性，我的解决方案使用二次算法将每个点与集合中的每个其他点进行比较。但是我希望在线性或线性对数时间内解决这个问题，所以我需要帮助编写更高效的算法。

注意:x 和 y 值的大小非常大，所以我不能使用具有基于坐标大小的迭代的解决方案。

---

Answer 1

按 (x+y) 的降序对点进行排序，使用 (y-x) 的降序来打破平局。

然后，当您按顺序遍历点时，丢弃与前一个未丢弃点的三角形重叠的点。

完成后剩下的点是那些没有被任何三角形重叠的点。

总复杂度为 O(N log N)，主要是对点进行排序。

证明这是有效的是基于这样一个事实，即您保留的每个点的三角形包括与先前保留的点的三角形重叠的所有 future 点。