解題區►解題區 - 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;
}