UVa-10341 : Solve It

問題概要

区間[0,1]で単調減少な関数が与えられるので根を求める問題。

解法

二分探索。浮動小数点数のせいで端点の処理が面倒くさい。

acceptされたコード

計算量O(iter)。

#include <cstdio>
#include <cmath>
using namespace std;

double EPS = 1e-9;
int p, q, r, s, t, u;

double calc(double x){
	return p*exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u;
}

void solve(){
	double low = 0.0, high = 1.0;
	double lval = calc(low), hval = calc(high);
	if( (fabs(lval) < EPS && fabs(hval) < EPS) || lval < -EPS || hval > EPS){
		puts("No solution");
		return ;
	}

	for(int loop=0; loop<100; loop++){
		double mid = (high + low) / 2.0;
		if( calc(mid) > 0 ){
			low = mid;
		}
		else{
			high = mid;
		}
	}
	printf("%.4f\n", low + EPS);
}

int main(){
	while(scanf("%d%d%d%d%d%d", &p, &q, &r, &s, &t, &u) != EOF){
		solve();
	}

	return 0;
}