hdu 2348 Turn the corner(三分&&幾何)(中等)

 

Turn the corner

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2229 Accepted Submission(s): 856


Problem Description Mr. West bought a new car! So he is travelling around the city.

One day he comes to a vertical corner. The street he is currently in has a width x, the street he wants to turn to has a width y. The car has a length l and a width d.

Can Mr. West go across the corner?

 

 

Input Every line has four real numbers, x, y, l and w.
Proceed to the end of file.

Output If he can go across the corner, print yes. Print no otherwise.

Sample Input

10 6 13.5 4
10 6 14.5 4

Sample Output

yes
no

 

 

 

題意：

已知汽車的長和寬，l和w，以及倆條路的寬為x和y，汽車所處道路寬為x ，問汽車能否順利轉彎？

分析：汽車能否順利轉彎取決於在極限情況下，隨著角度的變化，汽車離對面路的距離是否大於等於0

如圖中

 

 

在上圖中需要計算轉彎過程中h 的最大值是否小於等於y很明顯，隨著角度θ的增大，最大高度ｈ先增長後減小，即為凸性函數，可以用三分法來求解

 

代碼：

 

#include
#include
#include
#include
using namespace std;
#define pi 3.141592653
double x,y,l,w;
double cal(double a)
{
    double s=l*cos(a)+w*sin(a)-x;
    double h=s*tan(a)+w*cos(a);
    return h;
}
int main()
{
    while(scanf(%lf %lf %lf %lf,&x,&y,&l,&w)!=EOF)
    {
        double left=0.0,right=pi/2;
        double lm,rm;
        while(fabs(right-left)>1e-6)
        {
            lm=(left*2.0+right)/3.0;
            rm=(left+right*2.0)/3.0;
            if(cal(lm)>cal(rm))
                right=rm;
            else left=lm;
        }
        if(cal(left)<=y)
            printf(yes
);
        else printf(no
);
    }
    return 0;
}