【三分法】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

题目大意：

给出街道在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/;

        while(fabs(r-le)>1e-)

        {

            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

最新文章

热门文章