题目177：整数角四边形

欧拉计划

Integer angled Quadrilaterals

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.

题目：

令 ABCD 为凸四边形，AC 和 BD 为对角线。在每一个顶点，对角线与相交的两边分别形成一个角，这样一共形成了 8 个角。

例如，在顶点 A，形成的两个角为 CAD，CAB。

如果这 8 个角以度为单位全部是整数的话，我们称这个四边形为“整数角四边形”。例如正方形就是一个整数角四边形，8 个角里每个都是 45°。如下例子也是一个整数角四边形：DAC = 20°, BAC = 60°, ABD = 50°, CBD = 30°, BCA = 40°, DCA = 30°, CDB = 80°, ADB = 50°。

不相似的整数角四边形一共有多少个？

注意：在计算角度时，如果度数与整数的差在 10^-9 以内，就可以认为是一个整数角度。

QingXin

        我觉得吧，这道题， 比起算角度，数四边形才是应该关注的事。如果直接进行四重循环，每次从1度到179度，要进行179*179*179*179=1026625681次循环，1分钟之内算完是比较吃力的，此外还要查重。
        所以，从减少循环下手。首先从四边形的四个角出发，选取其中最大的一个角（可与其他角并列最大），假定它是DCB。这个大角会唯一对应一个三角形DCB，再假定剩下的两个角中BDC是那个较小的（可并列最小），这样，循环时，应满足：
DCB >= CBA >= CBD+1
DCB >= CDA >= BDC+1
BDC <= CBD
这样，结合三角形内角和180度就得到了三角形CBD的循环条件：for DCB in range(61,180)，for BDC in range(max(180-DCB-DCB+1,1),int((180-DCB)/2)+1)。
同样的，BDC的相邻角ADB，CBD的相邻角DBA也应满足相似的条件：
DCB >= CBA = CBD+DBA
DCB >= CDA = BDC+ADB
DCB >= DAB = 180-ADB-DBA

如此，可以从原来循环的10亿+下降到一千万+，测整数角神马的就是三角函数知识啦，只要一个小角CAD是整数，其他的拿180度减一减，就都是整数角啦。最后结果 132695，不到1分钟左右算完。

1. import math
   
2. sind={}
   
3. cosd={}
   
4. for i in range(1,180):
   
5.     sind[i] = math.sin(i/180*math.pi)
   
6.     cosd[i] = math.cos(i/180*math.pi)
   
7. num=0
   
8. for DCB in range(61,180):
   
9.     for BDC in range(max(180-DCB-DCB+1,1),int((180-DCB)/2)+1):
   
10.         CBD=180-DCB-BDC
    
11.         for ADB in range(1,DCB-BDC+1):
    
12.             for DBA in range(max(1,180-ADB-DCB),min(DCB-CBD+1,180-ADB)):
    
13.                 BD = 1
    
14.                 AD = BD/sind[180-ADB-DBA]*sind[DBA]
    
15.                 DC = BD/sind[DCB]*sind[CBD]
    
16.                 AC = math.sqrt(AD*AD+DC*DC-2*AD*DC*cosd[ADB+BDC])
    
17.                 CAD = math.asin(min(sind[ADB+BDC]/AC*DC,1))/math.pi*180
    
18.                 if abs(CAD - round(CAD))<10**-9:
    
19.                     num+=1
    
20. print(num)

复制代码