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

Integer angled Quadrilaterals 题号:177 难度: 80 中英对照

Let ABCD be a convex quadrilateral, with diagonals AC and BD. At each vertex the diagonal makes an angle with each of the two sides, creating eight corner angles.

For example, at vertex A, the two angles are CAD, CAB.

We call such a quadrilateral for which all eight corner angles have integer values when measured in degrees an "integer angled quadrilateral". An example of an integer angled quadrilateral is a square, where all eight corner angles are 45°. Another example is given by DAC = 20°, BAC = 60°, ABD = 50°, CBD = 30°, BCA = 40°, DCA = 30°, CDB = 80°, ADB = 50°.

What is the total number of non-similar integer angled quadrilaterals?

Note: In your calculations you may assume that a calculated angle is integral if it is within a tolerance of 10-9 of an integer value.


Solution

为了形象,在二维直角坐标系下描述: 设原点为$A$点,$(1,0)$点为$B$点,$CD$在$x$轴上方。 设$∠DAB=a,∠DBA=b,AD=c;∠CAB=f,∠CBA=d,BC=e$。 由于$AB=1$及正弦定理,有$c=sin(b)/sin(a+b),e=sin(f)/sin(d+f)$。 过$D$点作$x$轴正向的平行射线,射线方向记为$E$,设$∠CDE=x$。 则由正切的定义可得: $$x=arctan(\frac{esin(f)-csin(a)}{ecos(f)-ccos(a)})$$ 则$∠CDA=g=180-a+y,∠DCB=180-d-y$ 对$a,b,d,f$四重循环枚举,然后判定各角是否为整数即可。

Code

public final class p177 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

    static final int prime[]=new int[]{2,3,5,7,11,13,17,19,23};
	
	static public String run() {
		int ans = 0;
		double[] sin = new double[180], cos = new double[180];

		for (int x = 0; x < 180; sin[x] = Math.sin(Math.toRadians(x)), cos[x] = Math
				.cos(Math.toRadians(x++)))
			;
		for (int a = 1; a <= 90; a++)
			for (int b = 1; b < 180 - a; b++) {

				double c = sin[b] / sin[a + b];
				for (int d = Math.max(a, b + 1); d <= 180 - a; d++)
					for (int f = d == a ? b : 1; f < Math.min(a, 180 - d); f++) {

						double e = sin[d] / sin[d + f];
						double x = Math.toDegrees(Math.atan2(sin[f] * e
								- sin[a] * c, cos[f] * e - cos[a] * c));
						int y = (int) Math.round(x);
						int g = 180 - a + y, h = 180 - d - y;
						if (h < a)
							break;
						if (g < d)
							continue;
						if ((d == g) && (f > a / 2))
							continue;
						if ((h == a) && (b > d / 2))
							continue;
						if (Math.abs(x - y) < 1.0E-10)
							ans++;
					}
			}
		return ""+ans;
	}
	
	
}
129325
2805ms