zoj2614 Bridge（自适應Simpson公式+二分答案）

【題解】

首先求出分出的最少區間數：n=ceil(B/D)，ceil():向上取整

然後依據每一段的寬度w=B/n及弧長L/=n來求"深度"h即可，答案為：y=H-h

w,h可确定一條抛物線，其弧長L關于h單調遞增，考慮二分h，驗證弧長

設抛物線頂點為原點，由(w/2,d)在抛物線上可知其方程為：y=a*x^2，其中a=4*h/(w*w)

可導函數f(x)在區間[a,b]上的弧長：有公式(無法打出來)，可以用微元法來推導，公式中的積分部分用自适應Simpson公式來求

【代碼】

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
double w,h,_a;//_a:設 F(x)=_a*x^2
double F(double x)
{
	return sqrt(1+4*_a*_a*x*x);
}
double simpson(double a,double b)//三點simpson法 
{
	double c=(a+b)/2;
	return (b-a)/6*(F(a)+4*F(c)+F(b));
}
double asr(double a,double b,double eps,double A)//遞歸過程 
{
	double c=(a+b)/2,L=simpson(a,c),R=simpson(c,b);
	if(fabs(L+R-A)<=15*eps) return L+R+(L+R-A)/15;
	return asr(a,c,eps/2,L)+asr(c,b,eps/2,R);
}
int main()
{
	double H,L,left,right;
	int T,D,B,n,i;
	scanf("%d",&T);
	for(i=1;i<=T;i++)
	{
		scanf("%d%lf%d%lf",&D,&H,&B,&L);
		n=(B+D-1)/D;//平均分成的段數 
		L/=(double)n;//每段繩索長 
		w=(double)B/(double)n;//每段寬度 
		left=0;
		right=H;
		while(right-left>1e-4)//二分橋的"深度"h==H-y
		{
			h=(left+right)/2;
			_a=4*h/(w*w);
			if(2*asr(0,w/2,1e-4,simpson(0,w/2))<=L) left=h;
			else right=h;
		}
		if(i>1) printf("\n");
		printf("Case %d:\n%.2lf\n",i,H-h);
	}
	return 0;
}