competitive-programming/solved-uva/11648.cpp at master · the-redback/competitive-programming · GitHub

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
/**
 *                                   ____
 *       ____ ___  ____ ________  __/ __/
 *      / __ `__ \/ __ `/ ___/ / / / /_
 *     / / / / / / /_/ / /  / /_/ / __/
 *    /_/ /_/ /_/\__,_/_/   \__,_/_/
 *
 *    @link : https://the-redback.com
 */

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

#define mem(a, b) memset(a, b, sizeof(a))
#define pb        push_back
#define pp        pop_back
#define inf       10e9  // 10^9
#define eps       10e-9
#define NN        1000000

int main() {
    ios_base::sync_with_stdio(false);
    int t = 1, tc;
    double x, y, z, u, w, xx, yy, zz, d;
    double ab, cd, ad, bc;
    cin >> tc;
    while (tc--) {
        cin >> ab >> cd >> ad >> bc;
        d = ab - cd;
        x = ((ad * ad) - (bc * bc) + (d * d)) / (2 * d);
        y = d - x;

        double h = sqrt((ad * ad) - (x * x));
        double theta1 = acos(x / ad);
        double theta2 = acos(y / bc);
        double area = (cd + ab) * h * 0.5;
        double low = 0, high = h, mid;

        while (high - low > eps) {
            mid = (high + low) / 2.0;
            xx = mid / (tan(theta1));
            yy = mid / (tan(theta2));
            double miniArea = (cd + cd + xx + yy) * mid * 0.5;
            if (miniArea < area / 2.0)
                low = mid;
            else
                high = mid;
        }
        xx = mid / (sin(theta1));
        yy = mid / (sin(theta2));
        x = ad - xx;
        y = bc - yy;
        printf("Land #%d: %.6lf %.6lf\n", t++, x, y);
    }
    return 0;
}