ZeroJudge 解題筆記：c113. 00378 - Intersecting Lines

作者：王一哲
日期：2026年3月9日


ZeroJudge 題目連結：c113. 00378 - Intersecting Lines

解題想法

直線的方程式可以寫成 $$ ax + by + c = 0 $$ 如果線上的兩個點的座標為 $(x_1, y_1)$、$(x_2, y_2)$，代入上式可得 $$ ax_1 + by_1 + c = 0 ~~~~~ ax_2 + by_2 + c = 0 $$ 兩式相減可得 $$ ax_1 - ax_2 + by_1 - by_2 = 0 ~\Rightarrow~ a(x_1 - x_2) = b(y_2 - y_1) $$ $$ a = y_2 - y_1 ~~~~~ b = x_1 - x_2 ~~~~~ c = -ax_1 - by_1 = x_1(y_1 - y_2) + y_1(x_2 - x_1) $$ 題目給定另一條直線上的座標為 $(x_3, y_3)$、$(x_4, y_4)$，則方程式 $a'x + b'y + c' = 0$ 的係數為 $$ a' = y_4 - y_3 ~~~~~ b' = x_3 - x_4 ~~~~~ c' = -a'x_3 - b'y_3 = x_3(y_3 - y_4) + y_3(x_4 - x_3) $$ 如果兩條直線平行，則 $$ \frac{a}{b} = \frac{a'}{b'} ~\Rightarrow~ ab' = a'b $$ 如果兩條直線重合，除了上式之外還要再加上另外兩個條件 $$ \frac{a}{c} = \frac{a'}{c'} ~\Rightarrow~ ac' = a'c ~~~~~ \frac{b}{c} = \frac{b'}{c'} ~\Rightarrow~ bc' = b'c $$ 如果兩條直線只有一個交點，則 $$ ab'x + bb'y + cb' - (a'bx + b'by + c'b) = 0 ~\Rightarrow~ x = \frac{c'b - cb'}{ab' - a'b} $$ $$ aa'x + ba'y + ca' - (a'ax + b'ay + c'a) = 0 ~\Rightarrow~ y = \frac{c'a - ca'}{ba' - b'a} $$

Python 程式碼

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

def line_equation(x1, y1, x2, y2):
    a = y2 - y1
    b = x1 - x2
    c = x1*(y1 - y2) + y1*(x2 - x1)
    return a, b, c

print("INTERSECTING LINES OUTPUT")
n = int(input())
for _ in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
    a, b, c = line_equation(x1, y1, x2, y2)
    ap, bp, cp = line_equation(x3, y3, x4, y4)
    if a*bp == ap*b:
        if a*cp == ap*c and b*cp == c*bp: print("LINE")
        else: print("NONE")
    else:
        x = (cp*b - c*bp) / (a*bp - ap*b)
        y = (cp*a - c*ap) / (b*ap - bp*a)
        print(f"POINT {x:.2f} {y:.2f}")
print("END OF OUTPUT")

C++ 程式碼

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

#include <cstdio>

int main() {
    puts("INTERSECTING LINES OUTPUT");
    int n; scanf("%d", &n);
    for(int i=0; i<n; i++) {
        int x1, y1, x2, y2, x3, y3, x4, y4;
        scanf("%d %d %d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
        int a = y2 - y1, b = x1 - x2, c = x1*(y1 - y2) + y1*(x2 - x1);
        int ap = y4 - y3, bp = x3 - x4, cp = x3*(y3 - y4) + y3*(x4 - x3);
        if (a*bp == ap*b) {
            if (a*cp == ap*c && b*cp == c*bp) puts("LINE");
            else puts("NONE");
        } else {
            float x = 1.0*(cp*b - c*bp) / (a*bp - ap*b), y = 1.0*(cp*a - c*ap) / (b*ap - bp*a);
            printf("POINT %.2f %.2f\n", x, y);
        }
    }
    puts("END OF OUTPUT");
    return 0;
}