poj1905

这个题有两个难点

1、解方程

poj1905

图片大了点呵。。Retina屏的水果本就是不错!

这方程是超越方程,只有数值解,那怎么办呢?

2、二分单调性证明

证明如下:

上面的方程,另左边等于s,则可推得弧长s与h间关系如下:

poj1905

绘制该函数图像如下:

poj1905

可知该函数是随l和s单增的,故可用二分逼近。

poj1905

上图是刚才那个超越方程的隐函数围道图像,也可证明。

另提供几何证明(为什么h越大s越大,可以利用二分来逼近这h在给定s下的最大值)

poj1905

下面是代码:

#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

#define eps 1e-5

int main() {
	double L, n, c, s;
    double h;
	double r;
	while (cin >> L >> n >> c) {
		if (L < 0 && n < 0 && c < 0)
			break;
		double low = 0.0;
		double high = 0.5 * L;
		double mid;
		s = (1 + n * c) * L;
		while (high - low > eps) {
			mid = (low + high) / 2;
			r = (4 * mid * mid + L * L) / (8 * mid);
			if (2 * r * asin(L / (2 * r)) < s)
				low = mid;
			else
				high = mid;
		}
		h = mid;
		cout << fixed << setprecision(3) << h << endl;
	}
}


poj1905

上一篇:hdu 1505 City Game && hdu 1506 Largest Rectangle in a Histogram


下一篇:双连通缩点 POJ 1515