做题感悟:做完这题发现三分一定与数学知识相结合出现,而且不是简单的数学知识。
解题思路:关键是要找到小车的运动状态,下面是分析和公式推导。
在小车转弯过程中,黄线是不断地变化的,变化规律是先增大再减小(可以自己模拟一下,只要黄线最大值小于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 ; }