题目91：找出象限内直角三角形的数量

欧拉计划

Right triangles with integer coordinates

The points are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is,

Given that , how many right triangles can be formed?

  题目：

点 位于整数点坐标上，并且与原点 O(0,0) 相连接形成三角形 ΔOPQ。

当横纵坐标都位于 0 到 2 之间时（包括 0 和 2），也就是 时，一共可以形成 14 个直角三角形。

给定 , 一共能形成多少个直角三角形？

丹小怪

51

QingXin

总共运行了10s，最笨的办法，结果14234。

num=0
for x1 in range(0,51):
    for y1 in range(0,51):
        for x2 in range(0,51):
            for y2 in range(0,51):
                s1 = x1*x1 + y1*y1
                s2 = x2*x2 + y2*y2
                s3 = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)
                f = [s1,s2,s3]
                f.sort()
                if f[0] >0:
                    if f[0] + f[1] == f[2]:
                        num+=1
                        
print(num/2)

jerryxjr1220

14234.0
[Finished in 5.1s]

size = 50
count = 0
counted = []
for x1 in range(0, size + 1):
    for y1 in range(0, size + 1):
        for x2 in range (0, size + 1):
            for y2 in range(0, size + 1):
                c2 = x1**2 + y1**2
                a2 = (x2 -x1)**2 + (y2-y1)**2
                b2 = x2**2 + y2**2
                if (c2 == a2 + b2 or a2 == b2 + c2 or b2 == a2 + c2) and a2 != 0 and b2 != 0 and c2 != 0:
                        count += 0.5
print(int(count))

jerryxjr1220

QingXin 发表于 2016-9-16 14:35
总共运行了10s，最笨的办法，结果14234。

和你的计算原理是一样的，但是比你快1倍的时间。
其实只要边长不为0即可，sort以后再额外判断2次很费时间的

QingXin

jerryxjr1220 发表于 2016-10-18 11:21
和你的计算原理是一样的，但是比你快1倍的时间。
其实只要边长不为0即可，sort以后再额外判断2次很费时 ...

恩，确实应该一次判断出来，sort搞麻烦了

芒果加黄桃

# encoding:utf-8
# 象限内直角三角形个数
from time import time

def euler090(N=50):
    count = 0
    # 直角顶点在X轴(1,0)--(50,0)
    count += 50 * 50
    # 直角顶点在Y轴(0,1)--(0,50)
    count += 50 * 50
    # 直角顶点在原点(0,0)
    count += 50 * 50
    for x1 in range(1, 51):
        for y1 in range(1, 51):
            for x2 in range(0, 51):
                for y2 in range(1, 51):
                    if not(x2 < x1 and y2 > y1):
                        continue
                    a = x1 * x1 + y1 * y1
                    c = x2 * x2 + y2 * y2
                    b = (x1 - x2) ** 2 + (y1 - y2) ** 2
                    if c == a + b:
                        count += 1
    for x1 in range(1, 51):
        for y1 in range(1, 51):
            for x2 in range(1, 51):
                for y2 in range(0, 51):
                    if not(x1 < x2 and y1 > y2):
                        continue
                    a = x1 * x1 + y1 * y1
                    c = x2 * x2 + y2 * y2
                    b = (x1 - x2) ** 2 + (y1 - y2) ** 2
                    if c == a + b:
                        count += 1
    print(count)
if __name__ == '__main__':
    start = time() 
    euler090()
    print('cost %.6f sec' % (time() - start))

14234
cost 6.564656 sec

永恒的蓝色梦想

from time import process_time as t
t1=t()
r=range(50+1)
count=0
for x1 in r:
  for x2 in r:
    for y1 in r:
      for y2 in r:
        if x1==x2 and y1==y2 or x1==0==y1 or x2==0==y2:continue
        l=sorted([(x1-x2)**2+(y1-y2)**2,x1**2+y1**2,x2**2+y2**2])
        if l[0]+l[1]==l[2]:count+=1
print(f'运行结果：{count/2}\n运行时间：{t()-t1}s')

运行结果：14234.0
运行时间：24.828125s

guoquanli

/*功能函数，实现直角三角形个数的计算*/
int calNumOfTag(int pointA){
        int tagNum = 0;
        int count = 0;
        for(int x1 = 0; x1 <= pointA; x1++){
                for(int y1 = 0; y1<=pointA; y1++){
                        for(int x2 = 0; x2 <= pointA; x2++){
                                for(int y2 = 0; y2<= pointA ; y2++){
                                        if((x1 == x2 && y1 == y2)|| (x1 == 0 && y1 == 0) || (x2 ==0 && y2 == 0)){
                                                continue;
                                        }
                                        //count++;
                                        //printf("符合条件的点的集合___%d____:A(%d,%d),B(%d,%d)\n",count,x1,y1,x2,y2);
                                        //printf("*******\n");
                                        int edge_1 = x1*x1 + y1*y1;
                                        //printf("edge_1 = x1*x1 + y1*y1[%d]\n",edge_1);
                                        int edge_2 = x2*x2 + y2*y2;
                                        //printf("edge_2 = x2*x2 + y2*y2[%d]\n",edge_2);
                                        int edge_3 = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 -y1);
                                        //printf("edge_3 = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 -y1)[%d]\n",edge_3);
                                        if(edge_1 + edge_2 == edge_3 || edge_1 + edge_3 == edge_2 || edge_3 + edge_2 == edge_1 ){
                                                tagNum++;
                                                //printf("能组成直角三角形的点是:B(%d,%d),C(%d,%d)\n",x1,y1,x2,y2);
                                        }
                                }
                        }
                }
        }
        return tagNum/2 ;

答案：14234

guosl

应用矢量代数里的叉积和点积来做，速度非常快

#include <iostream>
using namespace std;

int main(void)
{
  int N = 50;
  int nCount = 0;
  for (int x1 = 0; x1 <= N; ++x1)
  {
    for (int y1 = 0; y1 <= N; ++y1)
    {
      //遍历p1
      if (x1 == 0 && y1 == 0)//去掉原点
        continue;
      for (int x2 = 0; x2 <= N; ++x2)
      {
        for (int y2 = 0; y2 <= N; ++y2)
        {
          //遍历p2
          if ((x2 == 0 && y2 == 0) //去掉原点
            || (x1*y2 - x2 * y1 >= 0))//始终保持p1到p2为顺时针方向(应用叉积性质)
            continue;
          if ((y1*y2 == -x1 * x2) //直角在O点(应用内积性质)
            || (y1 * (y2 - y1) == -x1 * (x2 - x1)) //直角在p1点
            || (y2 * (y1 - y2) == -x2 * (x1 - x2)))//直角在p2点
            ++nCount;
        }
      }
    }
  }
  cout << nCount << endl;
  return 0;
}