POJ 2507 - Crossed ladders

http://poj.org/problem?id=2507

概要

幅 w の道が高い建物に挟まれている． x フィートの梯子が右側の建物をベースに左側の建物に立て掛けられており，y フィートの梯子が左側の建物をベースに右側の建物に立て掛けられている． この2つの梯子は地面から高さ c の点で交差している．

x, y, c が与えられたとき，w の値を答える．

制約

• 出力は 10^-3 の精度

解法

数式一発で求まる気がするけど，二分探索で求めた．

 1 #include <cstdio>
 2 #include <complex>
 3 #include <cmath>
 4 using namespace std;
 5 typedef complex<double> P;
 6 
 7 inline double cross(const P& a, const P& b)
 8 {
 9   return a.real()*b.imag() - b.real()*a.imag();
10 }
11 
12 struct segment
13 {
14   P a, b;
15   segment(const P& x, const P& y) : a(x), b(y) {}
16   inline P intersection(const segment& s) const
17   {
18     const P x = b - a;
19     const P y = s.b - s.a;
20     return a + x*(cross(y, s.a - a))/cross(y, x);
21   }
22 };
23 
24 int main()
25 {
26   double x, y, c;
27   while (scanf("%lf %lf %lf", &x, &y, &c) != EOF) {
28     double left = 0.0, right = min(x, y);
29     for (int i = 0; i < 100; i++) {
30       const double w = (left + right) / 2.0;
31       const segment s1(P(0.0, sqrt(x*x - w*w)), P(w, 0.0));
32       const segment s2(P(0.0, 0.0), P(w, sqrt(y*y - w*w)));
33       const P p = s1.intersection(s2);
34       if (p.imag() < c) {
35         right = w;
36       } else {
37         left = w;
38       }
39     }
40     printf("%.3f\n", (right + left)/2.0);
41   }
42   return 0;
43 }