Project Euler 264

题目

Triangle Centres

Consider all the triangles having:

• All their vertices on lattice points.
• Circumcentre at the origin \(O\).
• Orthocentre at the point \(H(5, 0)\).

There are nine such triangles having a perimeter \(\le 50\).

Listed and shown in ascending order of their perimeter, they are:

\(\begin{aligned} &A(-4, 3), B(5, 0), C(4, -3)\\ &A(4, 3), B(5, 0), C(-4, -3)\\ &A(-3, 4), B(5, 0), C(3, -4)\\ \\ \\ &A(3, 4), B(5, 0), C(-3, -4)\\ &A(0, 5), B(5, 0), C(0, -5)\\ &A(1, 8), B(8, -1), C(-4, -7)\\ \\ \\ &A(8, 1), B(1, -8), C(-4, 7)\\ &A(2, 9), B(9, -2), C(-6, -7)\\ &A(9, 2), B(2, -9), C(-6, 7)\\ \end{aligned}\)

The sum of their perimeters, rounded to four decimal places, is \(291.0089\).

Find all such triangles with a perimeter \(\le 10^5\).

Enter as your answer the sum of their perimeters rounded to four decimal places.

解决方案

欧拉线定理：在任意三角形中，外心、重心、垂心共线，且重心到垂心的距离是重心到外心的距离的两倍。

证明：设三角形 \(ABC\)，其外心为 \(O\)，重心为 \(G\)，垂心为 \(H\)。

以 \(O\) 为原点建立向量坐标系，设 \(\overrightarrow{OA} = \mathbf{a}\)，\(\overrightarrow{OB} = \mathbf{b}\)，\(\overrightarrow{OC} = \mathbf{c}\)，则 \(|\mathbf{a}| = |\mathbf{b}| = |\mathbf{c}| = R\)（\(R\) 为外接圆半径）。

垂心 \(H\) 满足 \(AH \perp BC\)，即 \((\overrightarrow{H} - \mathbf{a}) \cdot (\mathbf{b} - \mathbf{c}) = 0\)。代入 \(\overrightarrow{H} = \mathbf{a} + \mathbf{b} + \mathbf{c}\) 验证：

\[(\mathbf{a} + \mathbf{b} + \mathbf{c} - \mathbf{a}) \cdot (\mathbf{b} - \mathbf{c}) = (\mathbf{b} + \mathbf{c}) \cdot (\mathbf{b} - \mathbf{c}) = |\mathbf{b}|^2 - |\mathbf{c}|^2 = 0.\]

同理可验证 \(BH \perp AC\)。因此当 \(O\) 为原点时，\(\overrightarrow{H} = \mathbf{a} + \mathbf{b} + \mathbf{c}\)。

回归一般坐标系，有 \(\overrightarrow{OH} = \overrightarrow{OA} + \overrightarrow{OB} + \overrightarrow{OC}\)，即：

\[H = O + (\overrightarrow{OA} + \overrightarrow{OB} + \overrightarrow{OC}) = O + (A - O + B - O + C - O) = A + B + C - 2O.\]

又重心 \(G\) 满足 \(G = \dfrac{A + B + C}{3}\)，即 \(A + B + C = 3G\)。代入上式得：

\[H = 3G - 2O \Rightarrow H - G = 2(G - O).\]

所以 \(\overrightarrow{HG} = 2 \overrightarrow{GO}\)，即 \(O\)、\(G\)、\(H\) 三点共线，且 \(|HG| = 2|GO|\)。

由上面的结论，可以直接得出：重心\(G\)的坐标是\(\left(\dfrac{5}{3},0\right)\)。

假设\(A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)\)。那么有：\(x_1+x_2+x_3=5,y_1+y_2+y_3=0.\)

于是第三点被强制为\(C(x_3,y_3)=(5-x_1-x_2,-y_1-y_2).\)

由三点同在圆 \(x^2+y^2=R^2\) 上，得到

1. \(A,B\) 同半径：

   \[ x_2^2+y_2^2=x_1^2+y_1^2. \tag{B} \]

2. \(A,C\) 同半径，且用 \(x_3=5-x_1-x_2\)、\(y_3=-y_1-y_2\) 代入： \[ (5-x_1-x_2)^2+(-y_1-y_2)^2=x_1^2+y_1^2. \tag{C} \]

到此，几何条件已完全等价于整数方程系统 (B),(C) 加上线性关系。

联立\((1),(2)\)，化简后可以得到关于\(y_2\)的线性关系：

\[ 2y_1y_2=2(5-x_1)x_2-(5-x_1)^2-y_1^2. \tag{L} \]

由 \((B)\)：

\[ y_2^2=x_1^2+y_1^2-x_2^2. \tag{U2} \]

将 \((L)\) 两边平方并代入 \((U2)\)：

\[ 4y_1^2(x_1^2+y_1^2-x_2^2)=(2(5-x_1)x_2-(5-x_1)^2-y_1^2)^2. \tag{*} \]

为简化符号，令\(q=x_1-5, a=q^2+y_1^2=(x_1-5)^2+y_1^2.\)

注意 \(5-x_1=-q\)，则括号为

\[ 2(5-x_1)x_2-(5-x_1)^2-y_1^2=-2qx_2-q^2-y_1^2=-(2qx_2+a). \]

平方后符号无关，\((*)\) 等价于

\[ (2qx_2+a)^2=4y_1^2(x_1^2+y_1^2-x_2^2). \]

整理为关于 \(x_2\) 的二次方程，最终得到

\[ 4ax_2^2+4qax_2+(q^4-2(x_1^2+10x_1-25)y_1^2-3y_1^4)=0. \tag{Q} \]

把 \(q=x_1-5\)、\(a=(x_1-5)^2+y_1^2\) 展开即

\[ 4((x_1-5)^2+y_1^2)x_2^2 +4(x_1-5)((x_1-5)^2+y_1^2)x_2 +(x_1-5)^4-2(x_1^2+10x_1-25)y_1^2-3y_1^4=0. \]

可以得出结论：固定 \(A(x_1,y_1)\) 后，\(B\) 的横坐标 \(x_2\) 必须是该二次方程的整数根。因此对 \((Q)\) 记

\[ A_2=4a, B_2=4qa, C_2=q^4-2(x_1^2+10x_1-25)y_1^2-3y_1^4. \]

判别式

\[ \Delta=B_2^2-4A_2C_2 =16q^2a^2-16aC_2 =16a(q^2a-C_2). \]

计算括号内：

\[ q^2a=q^2(q^2+y_1^2)=q^4+q^2y_1^2, \]

因此

\[ q^2a-C_2 =(q^4+q^2y_1^2)-(q^4-2(x_1^2+10x_1-25)y_1^2-3y_1^4) =y_1^2(q^2+2(x_1^2+10x_1-25)+3y_1^2). \]

又因为 \(q^2=(x_1-5)^2=x_1^2-10x_1+25\)，所以

\[ q^2+2(x_1^2+10x_1-25) =(x_1^2-10x_1+25)+(2x_1^2+20x_1-50) =3x_1^2+10x_1-25. \]

于是

\[ q^2a-C_2=y_1^2(3x_1^2+10x_1+3y_1^2-25). \]

最终

\[ \Delta=16ay_1^2(3x_1^2+10x_1+3y_1^2-25). \]

定义

\[ e=a(3x_1^2+10x_1+3y_1^2-25), \]

则

\[ \Delta=16y_1^2e. \]

因此若要让 \(x_2\) 为整数解，必须先让 \(\Delta\) 成为完全平方数，从而要求 \(e\) 为完全平方数（再配合整除条件得到整数根）。

由求根公式可得，并写回\(q=x_1-5\)，得到：

\[ x_2=\frac{-B_2\pm\sqrt\Delta}{2A_2} =\frac{-4qa\pm 4y_1\sqrt e}{8a} =\frac{-qa\pm y_1\sqrt e}{2a} =\frac{-(x_1-5)a\pm y_1\sqrt e}{2a}. \]

因此当 \(e\) 为平方数时，仍需满足分子能被 \(2a\) 整除，才能使 \(x_2\) 为整数。

一旦得到整数 \(x_2\)，由 \((B)\) 得

\[ y_2^2=x_1^2+y_1^2-x_2^2. \]

必须要求右边是完全平方数，才能得到整数 \(y_2\)：

\[ y_2=\pm\sqrt{x_1^2+y_1^2-x_2^2}. \]

然后由线性约束恢复第三点：\(C(x_3,y_3)=(5-x_1-x_2,,-y_1-y_2).\)

最后再用同圆校验确保三点确实同半径。

不过，上述推导中隐含了除以 \(y_1\) 的可能性，因此当 \(y_1=0(\Delta=0)\) 时应回到原始条件。

当 \(y_1=0，(B)\) 变为

\[ y_2^2=x_1^2-x_2^2. \]

\((C)\) 变为

\[ (5-x_1-x_2)^2+y_2^2=x_1^2. \]

代入 \(y_2^2\)：

\[ (5-x_1-x_2)^2+x_1^2-x_2^2=x_1^2, \]

即

\[ (5-x_1-x_2)^2=x_2^2. \]

因此要么

\[ 5-x_1-x_2=x_2\Rightarrow x_2=\frac{5-x_1}{2}, \]

要么

\[ 5-x_1=0\Rightarrow x_1=5 \]

此时 \(A=H\) 会导致退化/不合法，应排除。

最终，对于每个整数点 \(A(x_1,y_1)\)，定义好\(q,a\)后，通过判别式计算出\(B(x_2,y_2)\)，并计算出\(C\)的坐标，并进行进一步判定即可。

代码

可见，\(x_1\ge -M/3-2,y_1\le M/3\)。此外，\(y_2\)还有一个上界：

上文由消元得到关于 \(x_2\) 的二次方程，其判别式可写为

\[ d=a(3x_1^2+10x_1+3y_1^2-25). \]

并且根能写成

\[ x_2=\frac{-(x_1-5)a\pm y_1\sqrt d}{2a}. \]

由于只枚举 \(y_1\ge 0\)，并选取使 \(x_2\) 落在排序区间（特别是 \(x_2\le x_3\)）的那一支，也就是取

\[ x_2=\frac{-(x_1-5)a-y_1\sqrt d}{2a}. \]

因为我们只统计满足 \(A<B<C\) 的那一套解，所以必须有\(x_1\le x_2\).代入上式并乘以正数 \(2a\)：

\[ 2ax_1 \le -(x_1-5)a - y_1\sqrt d. \]

移项得到

\[ y_1\sqrt d \le a(5-3x_1). \]

注意左边非负（因为 \(y_1\ge 0\) 且 \(\sqrt d\ge 0\)），因此右边也必须非负。

两边平方：

\[ y_1^2 d \le a^2(5-3x_1)^2. \]

代入 \(d=a(3x_1^2+10x_1+3y_1^2-25)\)，并约去一个 \(a>0\)：

\[ y_1^2(3x_1^2+10x_1+3y_1^2-25)\le a(5-3x_1)^2. \]

把 \(a=(x_1-5)^2+y_1^2\) 代回，就得到代码注释里的不等式形式：

\[ (5-3x_1)^2((x_1-5)^2+y_1^2)-y_1^2(3x_1^2+10x_1+3y_1^2-25)\ge 0. \]

令 \(s=y_1^2\)，再令

\[ k=3x_1^2-20x_1+25=x_1(3x_1-20)+25. \]

把上面的不等式整理（这一步是纯代数化简）会变成

\[ k^2+2ks-3s^2\ge 0. \]

这是一元二次不等式。解它可得在 \(s\ge 0\) 的情况下必须满足

\[ 0\le s \le k, \]

也就是

\[ y_1^2 \le 3x_1^2-20x_1+25=x_1(3x_1-20)+25. \]

由于我们只枚举 \(y_1\ge 0\)，最终得到

\[ 0\le y_1 \le \sqrt{x_1(3x_1-20)+25}. \]

这就是第二个上界的来源，而且它是由排序条件 \(x_1\le x_2\) 必然推出的可行域界。

代码

import math
from itertools import combinations

# 周长上限（题目要求 perimeter <= 1e5）
N = 100000

# 用集合去重：每个三角形用“排序后的三点坐标元组”作为唯一标识
# 形式为 ((x_a,y_a),(x_b,y_b),(x_c,y_c))，三点按字典序排序
st = set()


def check(x1, y1, x2, y2):
    """
    给定 A=(x1,y1), B=(x2,y2)，利用本题的关键向量恒等式确定 C，并做合法性校验与去重收集。

    关键恒等式（外心在原点时）：
        H = A + B + C  （向量相加）
    本题 H=(5,0)，因此：
        x1 + x2 + x3 = 5
        y1 + y2 + y3 = 0
    得到：
        C=(x3,y3)=(5-x1-x2, -y1-y2)

    外心在原点的条件是：
        |A| = |B| = |C|   （三点在同一以原点为圆心的圆上）
    在主循环里我们构造 B 时已经保证 |A|=|B|（用 y2^2 = |A|^2 - x2^2）
    因此这里只需要再检查 |A|=|C| 即可，保证 C 也在同圆上。

    最后把 (A,B,C) 三点排序，放入集合 st 去重。
    """
    # |A|^2 = x1^2 + y1^2
    dis2 = x1 ** 2 + y1 ** 2

    # 由 H=A+B+C=(5,0) 唯一确定 C
    x3 = 5 - x1 - x2
    y3 = -y1 - y2

    # 检查 |C|^2 == |A|^2，保证 C 在同一圆上
    if dis2 == x3 ** 2 + y3 ** 2:
        # 对三点排序，作为三角形的“标准表示”，用来去重
        pts = tuple(sorted([(x1, y1), (x2, y2), (x3, y3)]))

        # 过滤退化情况：
        # 如果 B 与 A 相同，或 B 与 C 相同，则三角形退化（有重复点）
        # 注意这里用 pts[1] 与 pts[0], pts[2] 比较，等价于“至少有两个点相同就不收”
        if pts[1] != pts[0] and pts[1] != pts[2]:
            st.add(pts)


# -------------------------
# 主搜索：枚举 A=(x1,y1)，再由代数条件构造 B=(x2,y2)，从而得到 C
# -------------------------

# x1 的枚举范围：
#   下界约为 -N/3（来自周长上界+排序约束的推导），这里额外减 2 做安全余量
#   上界取到 1（结合对称/排序去重策略，可以只枚举较小 x1）
for x1 in range(-N // 3 - 2, 2):
    # y1 的上界使用两个剪枝界的最小值：
    # 1) N/3 - |x1|：来自周长上界的粗剪枝（非严格但很有效）
    # 2) sqrt(x1*(3*x1-20)+25)：来自严格可行域（由 x1 <= x2 等排序约束推导）
    mx = min(
        N // 3 - abs(x1),
        int((x1 * (3 * x1 - 20) + 25) ** 0.5),
    )
    if mx < 0:
        continue

    # 经验剪枝：似乎总有 5 | (x1^2 + y1^2)
    # 因为平方 mod 5 只有 0,1,4：
    #   若 x1^2 ≡ 1，则 y1^2 需 ≡ 4 -> y1 ≡ 2 或 3 (mod 5)
    #   若 x1^2 ≡ 4，则 y1^2 需 ≡ 1 -> y1 ≡ 1 或 4 (mod 5)
    #   若 x1^2 ≡ 0，则 y1^2 需 ≡ 0 -> y1 ≡ 0 (mod 5)
    if x1 * x1 % 5 == 1:
        st_ls = [2, 3]
    elif x1 * x1 % 5 == 4:
        st_ls = [1, 4]
    else:
        st_ls = [0]

    # 枚举 y1（只枚举 y1>=0 的代表，再通过 check 里补充 y1 的符号对称）
    for m in st_ls:
        for y1 in range(m, mx + 1, 5):
            # 记 a = (x1-5)^2 + y1^2
            # 在推导中 a 常写作 (x1-5)^2 + y1^2
            a = (x1 - 5) ** 2 + y1 * y1

            # 判别式相关量：
            # 推导可得（固定 A=(x1,y1) 后）B 的 x 坐标 x2 满足一元二次方程，
            # 其判别式可写成：
            #   d = a * (3*x1^2 + 10*x1 + 3*y1^2 - 25)
            # 若 d 不是完全平方数，就不会得到整数 x2
            d = a * (3 * x1 * x1 + 10 * x1 + 3 * y1 * y1 - 25)
            if d < 0:
                continue

            # 需要 d 是完全平方数
            sd = math.isqrt(d)
            if sd ** 2 != d:
                continue

            # 由根公式可得一支候选：
            #   x2 = (-(x1-5)*a - y1*sqrt(d)) / (2a)
            # 要使 x2 为整数，分子必须能被 2a 整除
            tmp = -(x1 - 5) * a - y1 * sd
            if tmp % (2 * a) != 0:
                continue
            x2 = tmp // (2 * a)

            # 现在要恢复 y2。因为外心在原点要求 |A|=|B|：
            #   x1^2+y1^2 = x2^2+y2^2  =>  y2^2 = (x1^2+y1^2) - x2^2
            dis2 = x1 ** 2 + y1 ** 2
            y22 = dis2 - x2 * x2
            if y22 < 0:
                continue

            y2 = math.isqrt(y22)
            if y2 ** 2 != y22:
                continue

            # 至此得到一个候选 B=(x2,y2)（还未考虑 y2 的符号）
            # C 会由 H=A+B+C=(5,0) 唯一决定：
            #   C=(x3,y3)=(5-x1-x2, -y1-y2)
            # 这里先计算一次，主要是为了直观（check 内部会重新算）
            x3, y3 = 5 - x1 - x2, -y1 - y2

            # 由于 (x1,y1) 与 (x1,-y1) 在同一圆上，对称同样可能产生解；
            # (x2,y2) 与 (x2,-y2) 也同理。
            # 因此把 4 种符号组合都丢进 check，让 check 负责：
            #   - 生成 C
            #   - 验证 |A|=|C|
            #   - 排序去重加入 st
            check(x1, y1, x2, y2)
            check(x1, y1, x2, -y2)
            check(x1, -y1, x2, y2)
            check(x1, -y1, x2, -y2)

# -------------------------
# 汇总答案：对 st 中的每个三角形计算周长，若 <= N 则累加
# -------------------------

ans = 0.0
for tr in st:
    # tr 是三个点的排序元组：((x_a,y_a),(x_b,y_b),(x_c,y_c))
    # 计算周长：三条边的距离之和
    s = 0.0
    for p, q in combinations(tr, 2):
        # 组合取三对点：(A,B),(A,C),(B,C)，把三条边长度相加
        s += ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5

    # 只统计周长 <= N 的三角形（主循环剪枝只是“候选生成”，最终还要过周长关）
    if s <= N:
        ans += s

# 按题目要求输出 4 位小数
print(f"{ans:.4f}")