HDU ACM 2438 ->Turn the corner 3分求最值

HDU ACM 2438 ->Turn the corner 三分求最值

分析：主要参考http://m.blog.csdn.net/blog/yinzm520/22721285这里的解题方法。

关键是要找到小车的运动状态，下面是分析和公式推导；

在小车转弯过程中，黄线是不断地变化的，变化规律是先增大再减小。所以抓住这一点，用三分法。先找一个变量，角度sita（就是上图中用红色标记的那个角），之后就是一系列的推导，算出黄线的长度。角度的范围是（0，pi/2）。

当三分找出最长的黄线长度之后，使之与Y做比较，当它小于Y时，就说明能够通过了

最终可得到：f(angle)=a*sin(angle)+d/cos(angle)；又因为a=l-(x-d*sin(angle)/cos(angle)-d*tan(angle)。化简可得：f(angle)=l*sin(angle)-x*tan(angle)+d/cos(angle)。

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

double fx(double l,double x,double d,double angle)
{
	return l*sin(angle)-x*tan(angle)+d/cos(angle);
}

#define PI 3.141592654
#define esp 1e-8

int main()
{
	double x,y,l,w;
	double low,up,mid1,mid2,midv1,midv2;

	ios::sync_with_stdio(false);
	while(cin>>x>>y>>l>>w)
	{
		low=0;
		up=PI/2;    //区间[0,PI/2]相当于旋转了90度
		while(up-low>=esp)  //三分找出最大值
		{
			mid1=low+(up-low)/3;
			mid2=up-(up-low)/3;
			midv1=fx(l,x,w,mid1);
			midv2=fx(l,x,w,mid2);

			if(midv1<midv2)
				low=mid1;
			else
				up=mid2;
		}
		if(y-midv1>esp)
			cout<<"yes"<<endl;
		else
			cout<<"no"<<endl;
	}
    return 0;
}

HDU ACM 2438 ->Turn the corner 3分求最值

相关推荐