UVA 5788 Wally World：繞牆最短路徑幾何解法

UVA 5788 Wally World - 兩點繞線段最短路徑

題意：平面上兩點 A、B，有一條與坐標軸平行的線段牆 CD（不可穿越）。兩人以速度 1 移動，求最短會合時間（即最短路徑長度 / 2）。

幾何分析

1. 若線段 AB 與牆 CD 不相交：最短路徑即直線距離 |AB|。
2. 若相交：必須繞過牆的端點。最短路徑為 min( |AC|+|CB|, |AD|+|DB| )。即繞過 C 或繞過 D 取較小者。

因牆平行坐標軸，但算法對任意線段均適用。

線段相交判斷

用向量叉積判斷：
direction(p1,p2,p) = (p1-p)×(p2-p)
線段 p1p2 與 p3p4 相交條件：
(d1*d2 < 0 且 d3*d4 < 0) 或 任一端點在另一線段上（共線且在範圍內）。

代碼實現

struct Point { double x, y; };
double dist(Point a, Point b) { return hypot(a.x-b.x, a.y-b.y); }
double cross(Point a, Point b, Point c) { return (a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y); }
bool onSeg(Point a, Point b, Point p) { return min(a.x,b.x) <= p.x && p.x <= max(a.x,b.x) && min(a.y,b.y) <= p.y && p.y <= max(a.y,b.y); }
bool segIntersect(Point a, Point b, Point c, Point d) {
    double d1=cross(a,b,c), d2=cross(a,b,d), d3=cross(c,d,a), d4=cross(c,d,b);
    if (d1*d2<0 && d3*d4<0) return true;
    if (d1==0 && onSeg(a,b,c)) return true;
    if (d2==0 && onSeg(a,b,d)) return true;
    if (d3==0 && onSeg(c,d,a)) return true;
    if (d4==0 && onSeg(c,d,b)) return true;
    return false;
}
int main() {
    Point A,B,C,D; int cs=1;
    while (scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y)==4 && (A.x||A.y||B.x||B.y)) {
        scanf("%lf%lf%lf%lf",&C.x,&C.y,&D.x,&D.y);
        double ans = segIntersect(A,B,C,D) ? fmin(dist(A,C)+dist(C,B), dist(A,D)+dist(D,B)) : dist(A,B);
        printf("Case %d: %.3lf\n", cs++, ans/2.0);
    }
}

關鍵點

• 輸出時間 = 路徑長度 / 2（兩人同時移動）。
• 精度要求輸出小數點後 3 位 %.3lf。
• 線段相交判斷需處理共線端點在線段上情況。