POJ 2826 An Easy Problem?!：兩線段槽蓄水量計算幾何

問題描述

給定兩條線段（木板），形成一個槽，雨水垂直落下。求槽能蓄多少水。若兩線段不相交、平行、一條水平、或一條完全覆蓋另一條，則蓄水量為 0。否則計算交點與高點構成的三角形面積。

幾何分類討論

1. 相交判斷：用跨立實驗（叉積）判斷兩線段是否規範相交。不相交或共線重疊 → 0。
2. 水平線段：任一線段斜率為 0 → 0（水平無法蓄水）。
3. 覆蓋判斷：若一線段的兩端點都在另一線段「上方」（根據斜率符號與交點位置判斷），則無蓄水空間 → 0。
4. 一般情況：兩線段交於點 P，取兩線段較高端點 A, B，蓄水面積 = 三角形 PAB 面積 = |PA × PB| / 2。需根據 A, B 相對 P 位置計算三角形底高。

關鍵幾何工具

• 叉積 cross(a,b,c) 判斷轉向、面積。
• 直線交點求解（解線性方程組）。
• 點到直線距離、投影計算三角形高。

代碼邏輯框架

if (!segments_intersect(l1, l2)) ans=0;
else {
    P = intersection(l1, l2);
    A = higher_endpoint(l1); B = higher_endpoint(l2);
    if (P == A || P == B) ans=0; // 開口朝上
    else if (horizontal(l1) || horizontal(l2)) ans=0;
    else if (one_covers_other(l1, l2, P)) ans=0;
    else ans = triangle_area(P, A, B);
}

總結

POJ 2826 是計算幾何分類討論的典型題。關鍵在於全面覆蓋邊界情況（不相交、水平、覆蓋、端點重合），並正確計算三角形面積。代碼較長但邏輯清晰，適合作為幾何模板練習。