hdu2298 Toxophily

题意：射箭游戏，已知箭头的初始位置是（0,0），速度为v,靶的位置为（x，y），要求算出射中靶心的最小的角度，若不能射中，则输出-1

分析：借鉴之前几道三分的思想，很明显的一点是，关于高度h关于角度θ的函数是凸函数，首先三分枚举角度值，求出到达x时的最大高度

利用最大高度判断能否射中，若能，则继续二分θ逼近y，最后求出最小的θ

当然，此题还存在纯物理公式的解法

参考下面的博客

http://www.cnblogs.com/newpanderking/archive/2011/08/25/2153590.html

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define g 9.8
#define pi 3.141592653
double x,y,v;
double cal(double a)
{
    double vx=v*cos(a);
    double vy=v*sin(a);
    double t=x/vx;
    double h=vy*t-g*t*t/2;
    return h;
}
double ThiDiv()
{
    double left=0.0,right=pi/2,lm,rm;
    while(right-left>1e-8)
    {
        lm=(left*2.0+right)/3.0;
        rm=(left+right*2.0)/3.0;
        if(cal(lm)>cal(rm))
            right=rm;
        else left=lm;
    }
    return left;
}
double Bin_search(double angle)
{
    double left=0.0,right=angle,mid;
    while(right-left>1e-8)
    {
        mid=(left+right)/2.0;
        if(cal(mid)<y)
            left=mid;
        else right=mid;
    }
    return left;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf %lf %lf",&x,&y,&v);
        double angle=ThiDiv();
        double Maxh=cal(angle);
        if(Maxh<y)
            printf("-1\n");
        else if(fabs(Maxh-y)<=1e-8)
            printf("%.6f\n",angle);
        else 
            printf("%.6f\n",Bin_search(angle));
    }
    return 0;
}