当前位置:首页 » Project Euler » 详细页

Right triangles with integer coordinates 题号:91 难度: 25 中英对照

The points P (x1, y1) and Q (x2, y2) 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,
0 ≤ x1, y1, x2, y2 ≤ 2.


Given that 0 ≤ x1, y1, x2, y2 ≤ 50, how many right triangles can be formed?


Solution

题意要求:在x1、y1、x2、y2范围均在[0,50]范围内时,满足(x1,y1)(x2,y2)(0,0)这三点能组成的包含直角的三角形的个数 那么只要对x1、y1、x2、y2进行[0,50]的循环,再判断三点组成的三角形是否有个直角就可以 要注意的是,x1=0,y1=1,x2=1,y2=0和x1=1,y1=0,x2=0,y2=1是一样的三角形,为了避免重复,加上判断条件$$x1\times y2>x2\times y1$$ 对于一个边长分别为a,b,c的三角形,只要满足$$a^2+b^2==c^2$$或$$a^2+c^2==b^2$$或$$b^2+c^2==a^2$$即说明包含直角

Code

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public final class p91 {
	private static final int MAX_N=50;
	public static void main(String[] args){
		long start=System.nanoTime();
        long result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
	}
	public static long run(){
		long count=0;
		for(int x1=0;x1<=MAX_N;x1++){
			for(int y1=0;y1<=MAX_N;y1++){
				for(int x2=0;x2<=MAX_N;x2++){
					for(int y2=0;y2<=MAX_N;y2++){
						if(x1*y2>x2*y1&&isRight(x1,y1,x2,y2)){
							count++;
						}
					}
				}
			}
		}
		return count;
	}
	public static boolean isRight(int x1,int y1,int x2,int y2){

		int dx = x2 - x1;
		int dy = y2 - y1;
		return x1*x1 + y1*y1 + x2*x2 + y2*y2 == dx*dx + dy*dy
		    || x1*x1 + y1*y1 + dx*dx + dy*dy == x2*x2 + y2*y2
		    || x2*x2 + y2*y2 + dx*dx + dy*dy == x1*x1 + y1*y1;
	}
	
	
}
14234
28ms