[LA-3485] Bridge 基于定积分的二分

题面

传送门:LA-3485
题目大意:给定一个抛物线的左右长度和曲线长，求抛物线的底到顶部的距离。

样例

Sample Input
2
20 101 400 4042
1 2 3 4
Sample Output
Case 1:
1.00

Case 2:
1.60

思路

由上一篇的学习笔记中，我们已经说明过对于一个曲线函数f(x)，如果它的导函数为f’(x),那么在a,b这一段上的曲线长度为

$$\int_a^b\sqrt{1+[f'(x)]^2}dx$$ $$为什么是这个样子呢？我们可以把f‘(x)展开写成\\\\\Delta y/\Delta x\\\\ 那么在对于\Delta x 趋近于0的时候,(\Delta x)^2+(\Delta y)^2就相当于一个直角三角形斜边的平方.\\\\ 开根号,就是\sqrt{\frac{(\Delta y)^2}{(\Delta x)^2}+1}\\\\ 也就是\sqrt{[f'(x)]^2+1}$$

这里不免要运用这个去计算区间内的曲线长度。

读题，我们可以发现间隔总数为ceil(B/D).每个间隔宽度为(B/n).每个间隔的绳索长度为(L/n)

我们可以构造一个二次函数,它过0,0且开口向上。

假设w为宽,h为高

那么有a(w/2)^2 = h.

所以a = 4h/(w^2).

下面就是万恶的积分运算了！

这里积分我算了两次，第一次是自己没用a来去替换w和h算的,算是硬头皮算的，第二次就参考蓝书了。

第一次的计算方法:

经过一番试验。

double w,h = 1.0;
	cin >> w;
	while(1)
	{ 
		double ans = w*w/8/h*(log(abs(sqrt(16*h*h/w/w)+4*h/w)) + 4*h/w*sqrt(16*h*h/w/w+1))/2;
		h += 1.0;
		cout << ans << endl;
		system("pause");
	}

发现随着h的增加这个积分的值也在增加,这是个严格递增积分。
就可以用二分求解了！
写出这样的代码

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;

double D,H,B,L;
int T;
double F(double w,double h)
{
	double ans = w*w/8/h*(log(fabs(sqrt(16*h*h/w/w)+4*h/w)) + 4*h/w*sqrt(16*h*h/w/w+1))/2;
	ans *= 2;
	return ans;
}
double calc(double L,double w)
{
	double ll = 0.0,rr = H;
	//while(rr-ll > eps)
	for (int i=0;i<100;i++)
	{
		double mid = (ll+rr)/2;
		if (F(w,mid) - L > eps) rr = mid;
		else ll = mid;
	} 
	return (H-ll);
}
int main(int argc, char *argv[])
{
	scanf("%d",&T);
	for (int kase = 1; kase <= T; kase++)
	{
		printf("Case %d:\n",kase);
		scanf("%lf%lf%lf%lf",&D,&H,&B,&L);
		int n = ceil(B/D);
		double singleL = L/double(n);
		double singlew = B/double(n);
		//printf("##debug n:%d L:%.5lf w %.5lf\n",n,singleL,singlew);
		printf("%.5lf\n",calc(singleL,singlew));
	}
	return 0;
}

兴致勃勃地对样例，发现是正确的！！！

激动啊,自己造了几个凑好的数据发现都没有问题。

然后扔到OJ上就WA了,不管怎么调精度都是WA。

于是就考虑到这个方法可能存在误差。只不过很小很小但是在精度以内，会影响答案。

伤心，看到蓝书写的代换我真的头皮发麻

简化了a后发现其实积分中用t与dt代换x的步骤也省去了。

啊啊啊啊啊啊啊

难受

代码

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;

double D,H,B,LLL;
int T; 
double f(double a,double x)
{
    double aa = a*a,xx = x*x;
    return (x*sqrt(aa+xx) + aa*log(fabs(x+sqrt(aa+xx))))/2;
}
double calc(double w,double h)
{
	double a = 4*h/w/w;
	double b = 1/(2*a);
	return 4*a*(f(b,w/2)-f(b,0));
}
int main(int argc, char *argv[])
{
	scanf("%d",&T);
	for (int kase = 1; kase <= T; kase++)
	{
		if(kase > 1) printf("\n");
		printf("Case %d:\n",kase);
		scanf("%lf%lf%lf%lf",&D,&H,&B,&LLL);
		int n = ceil(B/D);
		double L = LLL/double(n);
		double w = B/double(n);
		double ll = 0.0,rr = H;
		while(rr-ll > eps)
		{
			double mid = (ll+rr)/2;
			if (calc(w,mid) - L > eps) rr = mid;
			else ll = mid;
		} 
		printf("%.2lf\n",H-ll);
	}
	return 0;
}