c – 给定第一象限中的坐标列表,计算可以形成多少个直角三角形,
发布时间：2020-12-16 09:31:54 所属栏目：百科 来源：网络整理
导读：给定第一象限中的坐标列表,计算可以从这些坐标中形成多少个直角三角形,其一侧平行于x轴,一侧平行于y轴. 最近我参加了一个编程竞赛,更具体地说是INOI(印度国家奥林匹克信息学),这是本文中两个问题中的第一个. 基本上我认为任何3点类型(a,y)(x,b)都会形成这样
|
给定第一象限中的坐标列表,计算可以从这些坐标中形成多少个直角三角形,其一侧平行于x轴,一侧平行于y轴.
最近我参加了一个编程竞赛,更具体地说是INOI(印度国家奥林匹克信息学),这是本文中两个问题中的第一个. 基本上我认为任何3点类型(a,y)(x,b)都会形成这样一个三角形,但无法更好地管理任何东西,最后只写了一个天真的O(n ^ 3)解决方案(所有朋友也是如此). 有谁能建议更好的方法？ 请,这不是家庭作业. 解决方法
让numX [i] =有多少个点有i作为它们的X坐标而numY [i] =有多少个点有i作为它们的Y坐标.
我们将计算某个点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)中运行. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |