现在的位置: 首页 > 综合 > 正文

HDU 2438 Turn the corner

2019年02月24日 ⁄ 综合 ⁄ 共 929字 ⁄ 字号 评论关闭

题目链接~~>

做题感悟:做完这题发现三分一定与数学知识相结合出现,而且不是简单的数学知识。

解题思路:关键是要找到小车的运动状态,下面是分析和公式推导。

在小车转弯过程中,黄线是不断地变化的,变化规律是先增大再减小(可以自己模拟一下,只要黄线最大值小于y,车就可以通过)。这样可以得到一个关于图中角度的公式,不断三分角度就可以得到最大的黄线长度了(采用三分是因为黄线所形成的函数是凸函数),角度(0 , PI / 2.0)。

代码:

#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
#define lld __int64
const double PI = 3.1415926535898 ;
const int INF = 99999999 ;
const double esp = 1e-8 ;
const int  mod= 10000007 ;
const int MX = 100005 ;
double x,y,l,d ;
double find(double k)
{
    return l*sin(k)-x*tan(k)+d/cos(k) ;
}
double third_search(double le,double rt)// 三分
{
    double mid,midd ;
    while(rt-le>=esp)
    {
        mid=(rt+le)/2.0 ;
        midd=(rt+mid)/2.0 ;
        find(mid) > find(midd) ? rt = midd : le=mid ;
    }
    return find(le) ;
}
int main()
{
    while(~scanf("%lf%lf%lf%lf",&x,&y,&l,&d))
    {
        if(third_search(0.0,PI/2.0)+esp<y)
                    printf("yes\n") ;
        else        printf("no\n") ;
    }
    return 0 ;
}

转自~~>

抱歉!评论已关闭.