UVA 10566：幾何 + 二分求解梯子交叉高度

問題描述

兩面牆寬度為 w，兩梯子長度分別為 x、y，底部分別抵住對側牆角，頂端交叉高度為 c。求牆寬 w。輸入多組 x, y, c，輸出 w（保留 3 位小數）。

幾何關係

設牆寬為 w，交叉點高度為 h。由相似三角形：

h / w1 = sqrt(y^2 - w^2) / w   (左梯子)
h / w2 = sqrt(x^2 - w^2) / w   (右梯子)
w1 + w2 = w

解得：1/h = 1/sqrt(x^2 - w^2) + 1/sqrt(y^2 - w^2)。
給定 h = c，求 w。函數 f(w) = 1/sqrt(x^2-w^2) + 1/sqrt(y^2-w^2) 在 (0, min(x,y)) 上嚴格遞增，f(0)=1/x+1/y，f(min)→+∞。若 c > 1/(1/x+1/y) 則無解（但題目保證有解）。

二分求解

• 搜索區間 l=0, r=min(x,y)。
• 迭代 100 次（雙精度充分）：
• mid = (l+r)/2，計算 h = 1 / (1/sqrt(x^2-mid^2) + 1/sqrt(y^2-mid^2))。
• 若 h > c 則 l = mid，否則 r = mid。
• 輸出 l（或 r）。

代碼實現

#include <bits/stdc++.h>
using namespace std;

struct Point { double x, y; };
Point operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }
Point operator+(Point a, Point b) { return {a.x+b.x, a.y+b.y}; }
Point operator*(Point a, double k) { return {a.x*k, a.y*k}; }
double cross(Point a, Point b) { return a.x*b.y - a.y*b.x; }

Point line_intersection(Point p, Point v, Point q, Point w) {
    Point u = p - q;
    double t = cross(w, u) / cross(v, w);
    return p + v * t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    double x, y, c;
    while (cin >> x >> y >> c) {
        double l = 0, r = min(x, y);
        for (int i = 0; i < 100; ++i) {
            double mid = (l + r) / 2;
            double h1 = sqrt(y*y - mid*mid);
            double h2 = sqrt(x*x - mid*mid);
            double h = 1.0 / (1.0/h1 + 1.0/h2);
            if (h > c) l = mid;
            else r = mid;
        }
        cout << fixed << setprecision(3) << l << '\n';
    }
    return 0;
}

複雜度

每組 O(100) 迭代，極快。

替代幾何解法

用座標幾何：左牆 (0,0)-(0,y)，右牆 (w,0)-(w,x)。梯子線段交點高度即為 c。二分 w 計算交點高度（如代碼所示），邏輯等價。