ZeroJudge 解題筆記：d055. 11437 - Triangle Fun

作者：王一哲
日期：2026年4月2日


ZeroJudge 題目連結：d055. 11437 - Triangle Fun

解題想法

數學題。分點公式是高中數學課程內容，假設要在兩個點 $A$、$B$ 找到另一個點 $C$，使 $\overline{AB} : \overline{CB} = m : n$，則 $$ C = \frac{n}{m+n} A + \frac{m}{m+n} B $$ 題目的提示中有由寫三角形三個頂點求面積的公式 $$ area = \frac{1}{2} \times \left | A_x B_y - A_y B_x + B_x C_y - C_x B_y + C_x A_y - C_y A_x \right | $$ 還要自己推導，由兩條不平行的直線端點求交點座標的公式。假設 $(x_1, y_1), (x_2, y_2)$ 是直線 $y = ax + b$ 的端點座標，$(x_3, y_3), (x_4, y_4)$ 是直線 $y = a'x + b'$ 的端點座標。將 $(x_1, y_1), (x_2, y_2)$ 代入 $y = ax + b$ 可得 $$ y_1 = ax_1 + b ~~~~~ y_2 = ax_2 + b $$ 利用加減消去法可得 $$ a = \frac{y_1 - y_2}{x_1 - x_2} ~~~~~ b = \frac{x_2 y_1 - x_1 y_2}{x_2 - x_1} $$ 同理可得 $$ a' = \frac{y_3 - y_4}{x_3 - x_4} ~~~~~ b' = \frac{x_4 y_3 - x_3 y_4}{x_4 - x_3} $$ 再求 $y = ax + b$ 與 $y = a'x + b'$ 的交點 $(x, y)$，利用加減消去法可得 $$ x = \frac{b' - b}{a - a'} ~~~~~ y = \frac{a'b - ab'}{a' - a} $$

Python 程式碼

使用時間約為 11 ms，記憶體約為 3 MB，通過測試。

def find_point(ax, ay, bx, by):
    """
    代入直線的兩個端點 A、B
    求與 A、B 距離比為 1:2 的座標
    """
    cx = (2*ax + bx) / 3
    cy = (2*ay + by) / 3
    return cx, cy

def intersection(x1, y1, x2, y2, x3, y3, x4, y4):
    """
    x1, y1, x2, y2 是一條直線 y = ax + b 的兩個端點
    x3, y3, x4, y5 是另一條直線 y = a'x + b' 的兩個端點
    兩條直線不平行，求直線的交點
    """
    a = (y1 - y2) / (x1 - x2)
    b = (x2*y1 - x1*y2) / (x2 - x1)
    ap = (y3 - y4) / (x3 - x4)
    bp = (x4*y3 - x3*y4) / (x4 - x3)
    x = (bp - b) / (a - ap)
    y = (ap*b - a*bp) / (ap - a)
    return x, y

def find_area(ax, ay, bx, by, cx, cy):
    """
    代入三角形 ABC 的三的頂點座標求面積
    """
    return abs(ax*by - ay*bx + bx*cy - by*cx + cx*ay - cy*ax)/2

t = int(input())
for _ in range(t):
    Ax, Ay, Bx, By, Cx, Cy = map(float, input().split())
    Dx, Dy = find_point(Bx, By, Cx, Cy)
    Ex, Ey = find_point(Cx, Cy, Ax, Ay)
    Fx, Fy = find_point(Ax, Ay, Bx, By)
    Px, Py = intersection(Bx, By, Ex, Ey, Ax, Ay, Dx, Dy)
    Qx, Qy = intersection(Bx, By, Ex, Ey, Cx, Cy, Fx, Fy)
    Rx, Ry = intersection(Ax, Ay, Dx, Dy, Cx, Cy, Fx, Fy)
    area = find_area(Px, Py, Qx, Qy, Rx, Ry)
    print(f"{round(area):d}")

C++ 程式碼

使用時間約為 1 ms，記憶體約為 120 kB，通過測試。

#include <cstdio>
#include <cmath>

struct Point {
    double x, y;
};

Point find_point(double ax, double ay, double bx, double by) {
    /* 代入直線的兩個端點 A、B       *
     * 求與 A、B 距離比為 1:2 的座標 */
    double cx = (2.0*ax + bx) / 3.0, cy = (2.0*ay + by) / 3.0;
    Point c;
    c.x = cx; c.y = cy;
    return c;
}

Point intersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
    /* x1, y1, x2, y2 是一條直線 y = ax + b 的兩個端點     *
     * x3, y3, x4, y5 是另一條直線 y = a'x + b' 的兩個端點 *
     * 兩條直線不平行，求直線的交點                        */
    double a = (y1 - y2) / (x1 - x2), b = (x2*y1 - x1*y2) / (x2 - x1);
    double ap = (y3 - y4) / (x3 - x4), bp = (x4*y3 - x3*y4) / (x4 - x3);
    double x = (bp - b) / (a - ap), y = (ap*b - a*bp) / (ap - a);
    Point c;
    c.x = x; c.y = y;
    return c;
}

double find_area(double ax, double ay, double bx, double by, double cx, double cy) {
    /* 代入三角形 ABC 的三的頂點座標求面積 */
    return abs(ax*by - ay*bx + bx*cy - by*cx + cx*ay - cy*ax)/2.0;
}

int main() {
    int t; scanf("%d", &t);
    for(int i=0; i<t; i++) {
        double Ax, Ay, Bx, By, Cx, Cy;
        scanf("%lf %lf %lf %lf %lf %lf", &Ax, &Ay, &Bx, &By, &Cx, &Cy);
        Point D, E, F, P, Q, R;
        D = find_point(Bx, By, Cx, Cy);
        E = find_point(Cx, Cy, Ax, Ay);
        F = find_point(Ax, Ay, Bx, By);
        P = intersection(Bx, By, E.x, E.y, Ax, Ay, D.x, D.y);
        Q = intersection(Bx, By, E.x, E.y, Cx, Cy, F.x, F.y);
        R = intersection(Ax, Ay, D.x, D.y, Cx, Cy, F.x, F.y);
        double area = find_area(P.x, P.y, Q.x, Q.y, R.x, R.y);
        printf("%d\n", (int)round(area));
    }
    return 0;
}