2507:Crossed ladders

keyword

幾何　2分探索　C++

概要

x,y,cが与えられたときに?の部分を求める問題。
相似とか使えば厳密解が出そうな雰囲気はあるけど、面倒そうなので2分探索で。?が大きくなればcは下がり、小さくなればcは増えるという単調性を利用する。幾何と2分探索ってどうしてこう相性がいいのだろう。

int main(){
    double x, y, c, high, low, mid;

    while(scanf("%lf%lf%lf",&x,&y,&c)!=EOF){
        low = 0.0;
        high = min(x,y) - EPS;
        mid = 0.5*(low + high);
        while(high - low >= 1e-5){
            mid = 0.5*(low + high);
            if(isLL(point(0.0,0.0), point(mid, sqrt(x*x-mid*mid)),
                  point(0.0,sqrt(y*y-mid*mid)), point(mid, 0.0)).imag() > c){
                low = mid;
            }
            else high = mid;
        }

        printf("%.3f\n", mid);
    }

    return 0;
}