uva 1356/LA 3485 Bridge 题解

题意：有一座桥，桥上等距摆若干个塔，高度H，宽度不计。相邻两个塔距离不超过D。有一个绳索，总长度为L，桥的长度为L，两个塔之间的绳索成全等的抛物线。求建最少的塔的时候绳索下端离地高度y。

白书上的例题。。我基本上是抄的代码。

间隔数n=ceil(B/D)，每个间隔宽度D'=B/n，之间的绳索长度L'=L/n。则抛物线的宽度已知，即D'。

根据微积分知识，可导函数f(x)在区间[a,b]上的弧长为\(\int_{b}^{a} \sqrt{1+[f'(x)]^2}dx\) 。

则此时抛物线的长度只与其高度h有关，且随h增单调递增，二分答案即可。

求积分用simpson比较好。好想也好写。

 1 #include<cstdio>
 2 #include<cmath>
 3 double a;
 4 inline double f(double x)
 5 {
 6     return sqrt(1+4*a*a*x*x);
 7 }
 8 inline double simpson(double a,double b)
 9 {
10     double c=a+(b-a)/2;
11     return (f(a)+4*f(c)+f(b))*(b-a)/6;
12 }
13 double asr(double a,double b,double eps,double A)
14 {
15     double c=a+(b-a)/2;
16     double L=simpson(a,c),R=simpson(c,b);
17     if(fabs(L+R-A)<=15*eps) return L+R+(L+R-A)/15.0;
18     else return asr(a,c,eps/2,L)+asr(c,b,eps/2,R);
19 }
20 int T;
21 int D,H,B,L;
22 int main()
23 {
24 //    freopen("1.in","r",stdin);
25     scanf("%d",&T);
26     for(int kase=1;kase<=T;++kase)
27     {
28         scanf("%d%d%d%d",&D,&H,&B,&L);
29         int n=(B+D-1)/D;
30         double D1=(double)B/n,L1=(double)L/n;
31         double x=0,y=H;
32         while(y-x>1e-7)
33         {
34             double m=x+(y-x)/2;
35             a=4*m/(D1*D1);
36             if(asr(0,D1/2,1e-6,simpson(0,D1/2))*2<L1) x=m;
37             else y=m;
38         }
39         if(kase>1) putchar(10);
40         printf("Case %d:\n%.2f\n",kase,H-x);
41     }
42     return 0;
43 }