Project Euler 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.

解决方案

本题在枚举的过程中需要注意旋转、翻转的情况，需要去重。需要通过一些手段尽量减少枚举量。

只需要枚举其中四个角$DAC,BAC,ABD,CBD$的大小，就可以通过正弦定理和余弦定理确定另外$4$个角的值，然后判断这些角是否都为整数。

具体过程见代码。

加上旋转，翻转后有八种方案，我们只保留其中一种。

代码

本代码根据题目下Thread的一份代码进行优化修改。

#include <bits/stdc++.h>
using namespace std;

double pi = acos(-1.0);
double sina[184];
double cosa[184];
unsigned hs(int a, int b, int c, int d) {
    return (a << 24) | (b << 16) | (c << 8) | d;
}

int main() {
    int ans = 0;
    for (int i = 0; i <= 180; i++) {
        sina[i] = sin(i * pi / 180);
        cosa[i] = cos(i * pi / 180);
    }
    // 不失一般性，枚举的角DAC是八个角中最小的。后续计算中如果发现有比这更小的角，则直接跳出循环。
    for (int DAC = 1; DAC <= 45; DAC++)
        // AB边上的另外两个角ABD，CBD至少有DAC这么大。
        for (int BAC = DAC; BAC <= 180 - DAC * 3; BAC++)
            // CBD至少有DAC这么大。
            for (int ABD = DAC; ABD <= 180 - 2 * DAC - BAC; ABD++)
                for (int CBD = DAC; CBD <= 180 - DAC - BAC - ABD; CBD++) {
                    int BCA = 180 - (BAC + ABD + CBD);
                    int ADB = 180 - (DAC + BAC + ABD);
                    // AB=1
                    double AC = sina[ABD + CBD] / sina[BCA];
                    double AD = sina[ABD] / sina[ADB];
                    double DC = sqrt(AC * AC + AD * AD - 2 * AC * AD * cosa[DAC]);
                    double tmpACD = acos((AC * AC + DC * DC - AD * AD) / (2 * AC * DC)) * 180 / pi;
                    int ACD = int(round(tmpACD));
                    if (fabs(tmpACD - ACD) > 1e-9) continue;
                    if (ACD < DAC) break;
                    int CDB = 180 - (DAC + ACD + ADB);
                    if (CDB < DAC) break;
                    unsigned h = hs(DAC, BAC, ABD, CBD);
                    if (h > hs(ABD, CBD, BCA, ACD)) continue;
                    if (h > hs(BCA, ACD, CDB, ADB)) continue;
                    if (h > hs(CDB, ADB, DAC, BAC)) continue;
                    if (h > hs(BAC, DAC, ADB, CDB)) continue;
                    if (h > hs(CBD, ABD, BAC, DAC)) continue;
                    if (h > hs(ACD, BCA, CBD, ABD)) continue;
                    if (h > hs(ADB, CDB, ACD, BCA)) continue;
                    ++ans;
                }
    printf("%d\n", ans);
    return 0;
}