给定第一象限中的坐标列表,计算可以形成多少直角三角形,其一侧与x轴平行

Question

给定一个坐标列表first quadrant,计算从这些坐标中可以形成多少个直角三角形,其中一个边平行于x-axis一边并且一边平行于y-axis.

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

基本上我认为任何3点类型(a,y) (x,y) (x,b)都会形成这样一个三角形,但无法更好地管理任何东西,最后只是写了一个天真的O(n ^ 3)解决方案(所有朋友也这样做了).

有谁能建议更好的方法？

请,这不是家庭作业.

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).