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

概述给定第一象限中的坐标列表,计算可以从这些坐标中形成多少个直角三角形,其一侧平行于x轴,一侧平行于y轴. 最近我参加了一个编程竞赛,更具体地说是INOI(印度国家奥林匹克信息学),这是本文中两个问题中的第一个. 基本上我认为任何3点类型(a,y)(x,y)(x,b)都会形成这样一个三角形,但无法更好地管理任何东西,最后只写了一个天真的O(n ^ 3)解决方案(所有朋友也是如此). 有谁能建议更好的方 给定第一象限中的坐标列表,计算可以从这些坐标中形成多少个直角三角形,其一侧平行于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 = 0for 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)中运行.

总结

以上是内存溢出为你收集整理的c – 给定第一象限中的坐标列表,计算可以形成多少个直角三角形,其一侧与x轴平行全部内容，希望文章能够帮你解决c – 给定第一象限中的坐标列表,计算可以形成多少个直角三角形,其一侧与x轴平行所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。