POJ 1269 Intersecting Lines：直線關係判斷與交點計算

題目大意

給定兩條直線（各由兩點確定），判斷它們的關係：重合（LINE）、平行不重合（NONE）、相交（輸出交點座標，保留兩位小數）。多組測資。

幾何邏輯

1. 共線判斷：兩點在另一直線上（叉積為 0）。
2. 平行判斷：方向向量叉積為 0（且不共線）。
3. 相交：求解線性方程組，注意垂直線（斜率不存在）單獨處理。

代碼實現

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

struct Point { double x, y; };
struct Line { Point s, e; };

double cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool collinear(Line l1, Line l2) {
    return fabs(cross(l1.s, l2.s, l2.e)) < 1e-9 && fabs(cross(l1.e, l2.s, l2.e)) < 1e-9;
}

bool parallel(Line l1, Line l2) {
    double dx1 = l1.s.x - l1.e.x, dy1 = l1.s.y - l1.e.y;
    double dx2 = l2.s.x - l2.e.x, dy2 = l2.s.y - l2.e.y;
    return fabs(dx1 * dy2 - dx2 * dy1) < 1e-9;
}

void intersect(Line l1, Line l2) {
    double x, y;
    // 處理垂直線
    if (fabs(l1.s.x - l1.e.x) < 1e-9) {
        double k2 = (l2.s.y - l2.e.y) / (l2.s.x - l2.e.x);
        double b2 = l2.s.y - k2 * l2.s.x;
        x = l1.s.x; y = k2 * x + b2;
    } else if (fabs(l2.s.x - l2.e.x) < 1e-9) {
        double k1 = (l1.s.y - l1.e.y) / (l1.s.x - l1.e.x);
        double b1 = l1.s.y - k1 * l1.s.x;
        x = l2.s.x; y = k1 * x + b1;
    } else {
        double k1 = (l1.s.y - l1.e.y) / (l1.s.x - l1.e.x);
        double b1 = l1.s.y - k1 * l1.s.x;
        double k2 = (l2.s.y - l2.e.y) / (l2.s.x - l2.e.x);
        double b2 = l2.s.y - k2 * l2.s.x;
        x = (b2 - b1) / (k1 - k2);
        y = k1 * x + b1;
    }
    printf("POINT %.2f %.2f\n", x, y);
}

int main() {
    int n; scanf("%d", &n);
    puts("INTERSECTING LINES OUTPUT");
    while (n--) {
        Line l1, l2;
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &l1.s.x, &l1.s.y, &l1.e.x, &l1.e.y, &l2.s.x, &l2.s.y, &l2.e.x, &l2.e.y);
        if (collinear(l1, l2)) puts("LINE");
        else if (parallel(l1, l2)) puts("NONE");
        else intersect(l1, l2);
    }
    puts("END OF OUTPUT");
    return 0;
}

關鍵點

• 用叉積判斷共線與平行，避免斜率計算誤差。
• 浮點比較用 EPS = 1e-9。
• 垂直線單獨處理，避免除零。
• 輸出格式嚴格：大寫、固定字串、小數點後兩位。

複雜度

• 每組測資 O(1)，總時間 O(N)。