c++ - 给定第一象限中的坐标列表，计算可以形成多少个单边平行于 x 轴的直角三角形

Question

给定第一象限中的坐标列表，计算有多少直角三角形可以由这些坐标组成，这些三角形的一边平行于x轴 并且一侧平行于 y 轴。

最近我参加了一个编程竞赛，更具体地说是 INOI(印度国家信息学奥林匹克竞赛)，这是论文中两个问题中的第一个。

基本上，我认为 (a,y) (x,y) (x,b) 类型的任何 3 个点都会形成这样的一个三角形但无法更好地处理任何事情，最后只是写了一个天真的 O(n^3) 解决方案(我所有的 friend 也是如此)。

谁能提出更好的方法？

拜托，这不是家庭作业。

Answer 1

让我们numX[i] = how many points have i as their X coordinate和 numY[i] = how many points have i as their Y coordinate .

我们将计算某个点存在多少个具有所需属性的三角形 p .不失一般性，我们可以假设 p是三角形成直角的点。

为此，我们需要一个具有相同 Y 的点坐标和一个相同X协调。那么这个算法怎么样:

compute numX and numY in O(n).
num = 0
for each point p in the given list of points
    num += (numX[p.X] - 1)*(numY[p.Y] - 1)

output num

基本上，我们可以将每个点与相同的 X 组合起来与每个点坐标相同 Y坐标以获得所需的三角形。我们减去 1以免算p本身。

这将在 O(n) 中运行.