POJ 1410 Intersection：線段與矩形相交判定

題目大意

給定線段兩端點與矩形左上、右下座標（座標不保證有序），判斷線段是否與矩形相交（含包含、相切、穿過）。

解題思路

1. 先將矩形座標標準化（x_l <= x_r, y_b <= y_t）。
2. 若線段兩端點皆在矩形內 → 相交。
3. 處理垂直線段（斜率不存在）與水平線段（斜率為 0）特殊情況。
4. 一般情況：求線段直線方程 y = kx + b，分別與矩形四條邊（x = x_l, x = x_r, y = y_b, y = y_t）求交點，判斷交點是否落在線段與矩形邊段上。

完整代碼

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

int x_s, y_s, x_e, y_e, x_l, y_t, x_r, y_b;

bool inX(int x) { return x >= x_l && x <= x_r; }
bool inY(int y) { return y >= y_b && y <= y_t; }
bool inSegX(int x) { return (x >= x_s && x <= x_e) || (x >= x_e && x <= x_s); }
bool inSegY(int y) { return (y >= y_s && y <= y_e) || (y >= y_e && y <= y_s); }
bool inRectY(double y) { return y >= y_b && y <= y_t; }
bool inRectX(double x) { return x >= x_l && x <= x_r; }

void swapIf(int &a, int &b) { if (a > b) swap(a, b); }

int main() {
    int n; scanf("%d", &n);
    while (n--) {
        scanf("%d%d%d%d%d%d%d%d", &x_s, &y_s, &x_e, &y_e, &x_l, &y_t, &x_r, &y_b);
        swapIf(x_l, x_r); swapIf(y_b, y_t);
        int a1=x_s, b1=y_s, a2=x_e, b2=y_e;
        swapIf(a1, a2); swapIf(b1, b2);

        if (inX(x_s) && inX(x_e) && inY(y_s) && inY(y_e)) { puts("T"); continue; }

        if (x_s == x_e) { // 垂直線段
            if (inX(x_s) && (inY(y_s) || inY(y_e) || (b1 <= y_b && b2 >= y_t))) { puts("T"); continue; }
        }
        if (y_s == y_e) { // 水平線段
            if (inY(y_s) && (inX(x_s) || inX(x_e) || (a1 <= x_l && a2 >= x_r))) { puts("T"); continue; }
        }

        double k = (y_s - y_e) * 1.0 / (x_s - x_e);
        double b = y_s * 1.0 - k * x_s;
        bool intersect = false;

        if (inSegX(x_l)) { double y = k * x_l + b; if (inRectY(y)) intersect = true; }
        if (!intersect && inSegX(x_r)) { double y = k * x_r + b; if (inRectY(y)) intersect = true; }
        if (!intersect && inSegY(y_b)) { double x = (y_b - b) / k; if (inRectX(x)) intersect = true; }
        if (!intersect && inSegY(y_t)) { double x = (y_t - b) / k; if (inRectX(x)) intersect = true; }

        puts(intersect ? "T" : "F");
    }
    return 0;
}

關鍵點總結

• 座標標準化避免大小關係錯誤。
• 垂直/水平線段單獨處理，避免除零。
• 交點判斷需同時滿足：在線段範圍內、在矩形邊範圍內。
• 輸出 T（相交）或 F（不相交）。