解題區/解題區 - UVa

UVa 1356 - Bridge

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給吊橋總長、塔與塔之間的纜線限制、塔的高度，纜線在塔與塔之間呈現拋物線，使用最少的塔，請問纜線離地面多高。

Sample Input

1
2
3
4
5
2
20 101 400 4042
1 2 3 4

Sample Output

1
2
3
4
5
Case 1:
1.00
Case 2:
1.60

Solution

可以藉由貪心得到塔的數量，但是拋物線的方程式並不明確，因此可以考慮二分的高度，來計算纜線夠不夠長。

得到拋物線方程式後，要計算拋物線長度，使用數值積分的方式得到。為了降低計算誤差，使用自適應辛普森積分法，也就是當預估方法的變異小到一定程度時，停止分段求值。

integral parabola length

$$\int{\sqrt{dx^{2} + dy^{2}}} = \int{\sqrt{1 + dy^{2}/dx^{2}} dx} \\ = \int{\sqrt{1 + f'(x)^{2}} dx}$$ 
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
#include <stdio.h> 
#include <math.h>
using namespace std;
class SimpsonIntegral {
public:
    const double eps = 1e-6;
    double a; // function coefficient
    double f(double x) { // usually replace
        return sqrt(1 + 4 * a * a * x * x);
    }
    void setCoefficient(double a) {
        this->a = a;
    } 
    double simpson(double a, double b, double fa, double fb, double fab) {
        return (fa + 4 * fab + fb) * (b - a) / 6.0;
    }
    double integral(double l, double r) {
        return integral(l, r, eps);
    }
private:
    double integral(double a, double b, double c, double eps, double A, double fa, double fb, double fc) {
        double ab = (a + b)/2, bc = (b + c)/2;
        double fab = f(ab), fbc = f(bc);
        double L = simpson(a, b, fa, fb, fab), R = simpson(b, c, fb, fc, fbc);
        if (fabs(L + R - A) <= 15 * eps)
            return L + R + (L + R - A) / 15.0;
        return integral(a, ab, b, eps/2, L, fa, fab, fb) + integral(b, bc, c, eps/2, R, fb, fbc, fc);
    }
    double integral(double a, double b, double eps) {
        double ab = (a + b) /2;
        double fa = f(a), fb = f(b), fab = f(ab);
        return integral(a, ab, b, eps, simpson(a, b, fa, fb, fab), fa, fab, fb);
    }
} tool;
// integral parabola length
// \int \sqrt_{dx^{2} + dy^{2}} = \int \sqrt_{1 + dy^{2}/dx^{2}} dx
// = \int \sqrt_{1 + f'(x)^{2}} dx
int main() {
    int testcase, cases = 0;
    double D, H, B, L;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf %lf %lf %lf", &D, &H, &B, &L);
        int n = ceil(B / D);
        double w = B / n, plen = L / n; // for a parabola
        double l = 0, r = H, len, mid;
        for (int it = 0; it < 100; it++) {
            mid = (l + r)/2; // parabola y = ax^2, pass (w/2, mid)
            tool.setCoefficient(4 * mid / w / w);
            len = 2 * tool.integral(0, w/2);
            if (len < plen)
                l = mid;
            else
                r = mid;
        }
        if (cases)	puts("");
        printf("Case %d:\n", ++cases);
        printf("%.2lf\n", H - l);
    }
    return 0;
}