首页 > 代码库 > 【三分法】hdu2438 Turn the corner

【三分法】hdu2438 Turn the corner

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
 
题目大意:
 
给出街道在x轴的宽度X,y轴的宽度Y,还有车的长l和宽w,判断是否能够转弯成功。
 
题解:
 
如图:
技术分享

 

可以很容易地观察到上面这样一条不等式:
而这个不等式可以很容易地观察出三分性质。
所以求解就很easy了。
 
代码如下:
 
#include<cstdio>
#include<cmath>
#include<iostream>
#define PI 3.14159
using namespace std;

double x,y,l,d;

double pd(double a)
{
    return sin(a)*l+d/cos(a)-y*tan(a);
}

int main()
{
    while(scanf("%lf%lf%lf%lf",&x,&y,&l,&d)!=EOF)
    {
        double lm,rm,le=0.0,r=PI/2;
        while(fabs(r-le)>1e-6)
        {
            lm=(le*2.0+r)/3.0;
            rm=(le+r*2.0)/3.0;
            if(pd(lm)>pd(rm)) r=rm;
            else le=lm;
        }
        if(pd(le)<=y)
            printf("yes\n");
        else
            printf("no\n");
    }
}

【三分法】hdu2438 Turn the corner