heru 1280 Turn the corner(08哈尔滨网赛 三分)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：有一个直角弯道，两条路的宽分别为x,y,汽车的长为l,宽为w，问能否转过去。
用一个别人的图:
我们 将车子尽量靠在右边和下边的边界，以右下角为坐标原点，建立坐标系，写出车子的内边界的直线方程
即图中所示，斜率确定，然后上移。
那么这样就可以得到P点坐标，将Y=x代入，得到x/tan(a)-l/cos(a)-w*sin(a)。
我们只要求出最小值，如果大于-y便 可以转过去。
分析这个函数，首先求一次导
f’=l/cos^2(a)-x/sin^2(a)-w*cos(a)，没有明显的单调性。再求一次导
f''=2*l*sin(a)/cos^3(a)+2*x*cos(a)/sin^3(a)+w*sin(a)。
由于角度在0-90度之间，所以二阶导非负，为凹函数，三分求最小值。
注意还得特判初始宽度是否能够容纳
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#define eps 1e-7using namespace std;double x,y,l,w;double cal(double a){ return (x-l*sin(a)-w/cos(a))/tan(a);}int main(){ while(scanf("%lf%lf%lf%lf",&x,&y,&l,&w)!=EOF){ double low=0,high=acos(-1.0)/2,mid,midd; while(fabs(high-low)>eps){ mid=(low+high)/2; midd=(mid+high)/2; if(cal(mid)<cal(midd)) high=midd; else low=mid; } if(cal(low)<-y||x<w||y<w) puts("no"); else puts("yes"); } return 0;}