HDOJ（2438）几何里的三分

Turn the corner

http://acm.hdu.edu.cn/showproblem.php?pid=2438

题目：一辆车能否在一个路口拐弯，看图就很明白啦。

算法：见下图，只要求出图中明黄色线段的最大值小于y就可以了。一图抵千言。

 #include <iostream>

 #include <cmath>

 using namespace std;

 double x,y,l,d;

 double f_angle(double angle)

 {

     return l*cos(angle)+d/sin(angle)-x/tan(angle);

 }

 int main()

 {

     double mid1,mid2,low,high;

     while(cin>>x>>y>>l>>d)

     {

         low=0.0;

         high=acos(-1.0)/;

         while(high-low>=1.0e-6)

         {

             //三分法求极值

             mid1=low+(high-low)/3.0;

             mid2=high-(high-low)/3.0;

             if(f_angle(mid1)<=f_angle(mid2))

                 low=mid1;

             else

                 high=mid2;

         }

         if(f_angle(low)<y)

             cout<<"yes"<<endl;

         else

             cout<<"no"<<endl;

     }

     return ;

 }

二分查找所面向的搜索序列的要求是：具有单调性（不一定严格单调）；

与二分查找不同的是，三分法所面向的搜索序列的要求是：序列为一个凸性函数（包括上凸和下凸）。