欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Turn the corner(三分)

程序员文章站 2022-06-04 16:37:50
...

Turn the corner

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?
Turn 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

思路:
题目是问车子能否拐过这个拐角。能的话就打印“yes”,不能就打印“no”。在通过分析后可以得到,随着汽车由x进入y,图中h的高度先增大后减小,而解几何图形后可得:
s = l * cos(θ) + w * sin(θ) - x ;
h =s * tan(θ) + w * cos(θ);
这个函数是一个先增后减的凸函数,所以用三分法。
刚开始的时候我的三分是写成这样的
m1 = (a+b) / 2;
m2 = (m1+b) / 2;
但是WA了,后来又想了想改成了:
m1 = (2a+b) / 3;
m2 = (a+2
b) / 3;
见图:
Turn the corner(三分)

完整代码:

#include<iostream>
#include<cmath>
using namespace std;
double x,y,l,w;
const double eps=1e-10;
double pi=acos(-1.0);

double f(double n)      //函数关系
{
    double s=l*cos(n)+w*sin(n)-x;
    double h=s*tan(n)+w*cos(n);
    return h;
}
void thrp() //三分
{
    double m1,m2;
    double a=0.0;
    double b=pi/2;
    while(b-a>=eps)
    {
        m1=(2*a+b)/3;
        m2=(a+2*b)/3;
        if(f(m2)-f(m1)>=eps)
        {
            a=m1;
        }
        else
        {
            b=m2;
        }
    }
    if(f(m1)<=y)
    {
        cout<<"yes"<<endl;
    }
    else
    {
        cout<<"no"<<endl;
    }
}
int main()
{
    while(cin>>x>>y>>l>>w)
    {
        thrp();
    }
    return 0;
}