Morris' Blog

2012-06-07 21:54:03Morris

[UVA][二分] 10566 - Crossed Ladders

留言 0 收藏 0 推薦 0

Problem H

Crossed Ladders

Input: Standard Input
Output: Standard Output
Time Limit: 1 Second
 
A narrow street is lined with tall
buildings. An x foot long ladder is rested at the base of the building
on the right side of the street and leans on the building on the left side. A y
foot long ladder is rested at the base of the building on the left side of the
street and leans on the building on the right side. The point where the two
ladders cross is exactly c feet from the ground. How wide is the street?

Each
line of input contains three positive floating point numbers giving the values
of x, y, and c. 
For
each line of input, output one line with a floating point number giving the
width of the street in feet, with three decimal digits in the fraction. 
Sample Input                             Output for Sample
Input
 
  30 40 1012.619429 8.163332 310 10 310 10 1 
  26.0337.0008.0009.798
 

做法 : 二分答案
利用相似形的觀念可以得到當距離 d 被決定的時候, c 的解

#include <stdio.h>
#include <math.h>
#define eps 1e-5

int main() {
    double c, x, y;
    while(scanf("%lf %lf %lf", &x, &y, &c) == 3) {
        double l = 0, r = x < y ? x : y, d, tc;
        while(1) {
            d = (l+r)/2;
            tc = sqrt(y*y-d*d)*sqrt(x*x-d*d)/(sqrt(y*y-d*d)+sqrt(x*x-d*d));
            if(fabs(tc-c) <= eps)
                break;
            if(tc > c)
                l = d;
            else
                r = d;
        }
        printf("%.3lf\n", d);
    }
    return 0;
}