LightOj 1062 (Crossed Ladders)

#lightoj #cp #problem_solving #binary_search #geometry

Idea

Binary Search / Geometry

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

/** Which of the favors of your Lord will you deny ? **/

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

#define LL long long
#define PII pair<int,int>
#define PLI pair<LL,int>
#define LPII pair<LL, pair<int,int> >
#define MP make_pair
#define F first
#define S second
#define LINF LLONG_MAX

//#define EPS 1e-11
double INF=1e100;
double EPS=1e-12;

struct PT
{
    double x,y;
    PT() {}
    PT(double x,double y) : x(x), y(y) {}
    PT(const PT &p) :   x(p.x), y(p.y) {}

    PT operator + (const PT &p) const
    {
        return PT(x+p.x, y+p.y);
    }
    PT operator - (const PT &p) const
    {
        return PT(x-p.x, y-p.y);
    }
    PT operator * (double c)    const
    {
        return PT(x*c, y*c  );
    }
    PT operator / (double c)    const
    {
        return PT(x/c, y/c  );
    }
};

double dot(PT p, PT q)
{
    return p.x*q.x+p.y*q.y;
}
double cross(PT p, PT q)
{
    return p.x*q.y-p.y*q.x;
}

PT ComputeLineIntersection(PT a, PT b, PT c, PT d)
{
    b=b-a;
    d=c-d;
    c=c-a;
    assert(dot(b, b) > EPS && dot(d, d) > EPS);
    return a + b*cross(c, d)/cross(b, d);
}

const double eps = 1e-11;
int cmp(double x, double y)
{
    return (x <= y + eps) ? (x + eps < y) ? -1 : 0 : 1; /** 0 -> x equal y , 1 -> x>y , -1 -> x<y **/
}

int main()
{
    int tc;
    scanf("%d",&tc);

    //freopen("LightOj1056.txt","w",stdout);

    for(int i=1; i<=tc; i++)
    {
        double x,y,c,d;
        cin>>x>>y>>c;

        double lo=0,hi=min(x,y),mid;

        while(cmp(lo,hi)==-1)
        {
            mid=(lo+hi)*0.5;
            d=mid;

            double a1=sqrt(x*x-d*d);
            double a2=sqrt(y*y-d*d);

            PT h = ComputeLineIntersection(PT(0,0),PT(d,a2),PT(d,0),PT(0,a1));

            if (cmp(h.y, c) == 0)
                break;
            if (cmp(h.y, c) == 1)
                lo = mid;
            else
                hi = mid;

            d=mid;

        }

        cout<<"Case "<<i<<": "<<fixed<<setprecision(8)<<d<<endl;

    }

    return 0;

}