HDU 2438 Turn the corner (三分求极值)

HDU 2438 Turn the corner (三分求极值)

Turn the corner

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2920    Accepted Submission(s): 1150

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

Source

​​2008 Asia Harbin Regional Contest Online​​

Recommend

gaojie   |   We have carefully selected several similar problems for you:  ​​2444​​​ ​​2441​​​ ​​2442​​​ ​​2443​​​ ​​2440​​

题解：

可以根据边界，汽车已经转弯，设水平方向为x轴，垂直方向为y轴。

则汽车的内边界(靠近里面的边界)的直线方程式f(x)为：y=x*tan(a)+L*sin(a)+d/cos(a).其中a是汽车与x轴的夹角。

当y=X时，求解出的-x即为汽车的内边界到y轴的距离h，若h小于Y即可转弯，若大于Y就不能转弯。 所以只需要利用方程式，求-x的最大值，即可判断能否通过。 由于f(x)是凸函数(随着x的增大y先增大后减小)，所以，需要借助三分求极值来解决。

AC代码：

#include#include#include#include//const double Min=1e-7;using namespace std;double x,y,l,d;double solve(double a){ return (-x+l*sin(a)+d/cos(a))/tan(a); }int main(){ while(~scanf("%lf%lf%lf%lf",&x,&y,&l,&d)) { //90度换成弧度就是pi/2 double low=0,high=acos(-1.0)/2.0; double mid,mmid; if(x1e-8) //三分求极值 { mid=(low+high)/2.0; mmid=(mid+high)/2.0; if(solve(mid)>solve(mmid)) high=mmid; else low=mid; } if(solve(mid)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。