【二分】乗用車問題

1696 ワード

4乗用車問題
ソースプログラム名car.???(pas,c,cpp)実行可能ファイル名car.exeファイル名carを入力.inファイル名carを出力する.out
【問題の説明】
甲、乙二人は同時にA地を出発して、できるだけ早く同時にB地に到着しなければならない.出発時A地には乗用車が1台あったが、この乗用車は運転員のほかに1人しか連れて行けなかった.甲、乙の2人の歩行速度は同じで、車の速度より小さいことが知られている.問:どのように車を利用すれば、二人ができるだけ早く同時に到着することができますか.
【入力】
わずか1行、3つのデータはそれぞれAB両地の距離s、人の歩行速度a、車の速度bを表している.
【出力】
二人が同時にB地に到着するのに要する最短時間.
【例】
       car.in                                  car.out
       120 5 25                              9.6000000000E+00
O(1)アルゴリズムの問題です.しかし、二分でやることができます.簡単にしてください.
考えやすいのは、必然的に乗用車は一人一人しか乗せていないことだ.さもないと必ずこのように等価になる.
そのため、私たちは1人目の車に乗る長さを2人の時間で判断します.
2人目の乗車長をxとし、1人目と2人目の合計時間をそれぞれt 1,t 2とする
必然的にt 2はxと正相関し,t 1はxと負相関すると考えられる.
#include 
#include 

double mid;
const double eps = 1e-8;
double t1,t2,t3,l3,l4;
long s,a,b;

long getint()
{
	char tmp;long rs=0;bool sgn=1;
	do tmp=getchar();
	while (!isdigit(tmp)&&tmp-'-');
	if (tmp=='-'){tmp=getchar();sgn=0;}
	do rs=(rs<<3)+(rs<<1)+tmp-'0';
	while (isdigit(tmp=getchar()));
	return sgn?rs:-rs;
}

void calc()
{
	t2 = (mid/(double)b);
	l3 = mid - t2 * a;
	t3 = l3/(double)(b+a);
	l4 = ((double)s-mid+t3*b);
	t1 = t2 + t3 + (l4/(double)b);
	t2 = t2 + (double)(s-mid)/(double)a;
}

int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	
	s = getint();
	a = getint();
	b = getint();
	
	double l = 0;
	double r = s;
	
	while (r-l>-eps)
	{
		mid = (l+r)/2;
		calc(); 
		if (t1-t2-eps)
		{
			printf("%.40lf",t1);	
			break;
		}
		if (t1-t2>eps)
			r = mid-1e-9;
		else if (t1-t2