HDU-2298 Toxophily (三分法入门系列)

题意：

意大利炮射出炮弹的速度为v，求在(0,0)击中(x,y)处的目标，发射炮弹的角度。

题解：

设f(α)表示：角度为α，炮弹的横坐标与目标相同时，炮弹的高度。

f(α) = vsin(α) * t - 4.9 * t * t ①

t = x / ( v * cos(α) ) ②

然后，一顿乱搞得f(α) = x*tan(α) - (4.9 * x * x / v / v) * (tan(α) + 1)

妥妥的单峰函数，使用三分得出f(α)取max时的角度r。接下来在[0, r]上二分答

案即可（把tan(α)看成自变量，用二次函数的性质做，求角度r会比用三分更简

单）

PS: x = 0时，意大利炮往天上开，需要特判。

Trick：“三分 + 二分” 基础连招。

code：

#include <iostream>

#include <cmath>

using namespace std;

const double EPS = 1e-8;

int T; double x, y, v;

double f(double a)

{

    double t = x/(v*cos(a));

    return v*sin(a)*t - 9.8/2*t*t;

}

int main()

{

    cin >> T;

    while(T--)

    {

        cin >> x >> y >> v;

        double L = 0, R = acos(-1)/2-EPS;

        if(x==0) //特判，否则三角函数会智障掉

        {

            if(v*v/2/9.8 > y) printf("%.6lf\n", R);

            else printf("-1\n");

            continue;

        }

        for(int i=1;i<=100;i++)

        {

            double mid_L = (L+R) / 2;

            double mid_R = (mid_L+R) / 2;

            if(f(mid_L) > f(mid_R))

            {

                R = mid_R;

            } else {

                L = mid_L;

            }

        }

        if(f(L) < y) {printf("-1\n"); continue;}

        R = L, L = 0;

        for(int i=1;i<=100;i++)

        {

            double mid = (L+R)/2;

            if(f(mid) < y)

            {

                L = mid;

            } else {

                R = mid;

            }

        }

        printf("%.6lf\n", L);

    }

}

同类题：HDU5144

巴特西

HDU-2298 Toxophily (三分法入门系列)

最新文章

热门文章