Algoogle

Algorithm for Programming Contest

ACM-ICPC Tokyo Regional 2014 D Space Golf

Category: ICPC Tag: math

Space Golf

問題概要


弾を射出して距離dの位置の地面にちょうど当てたい.
バウンドがb回まで許される.
途中に障害物が立っているので避けなければならない.
以上を満たす最小の初速を求めよ

解法


バウンド回数ごとに分けて考える.
長さxを飛ばすのに必要な初速は発射角をとすると

つまり発射角は45度が基本的に最適.
45度で不可能なら可能な最小の角が最適.
正確には45度に一番近いものだが, 45度が無理ならそれ未満も無理なので最小の角になる.
あとはバウンド回数ごとにminを取れば良い

コード


(D.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
int n, b;
double d, p[16], h[16];

inline double sq(double x){ return x*x;}

bool intersect(double th, int i, int j, int k)
{
        const double bd = d/(k+1), pos = p[i] - bd*j;
        if(pos < 0 or bd < pos) return 0;
        const double v = sqrt(bd/sin(2*th)), vx = v*cos(th), vy = v*sin(th);
        const double y = -0.5*sq(pos)/sq(vx)+vy/vx*pos;
        return y < h[i];
}

bool attempt(double th, int k)
{
        for (int i = 0; i < n; i++)
                for (int j = 0; j <= k; j++)
                        if(intersect(th,i,j,k)) return 0;
        return 1;
}

double search(int k)
{
        double lb = pi/4, ub = pi, mid;
        for (int i = 0; i < 100; i++) {
                mid = (lb+ub)/2;
                if(attempt(mid,k)) ub = mid;
                else lb = mid;
        }
        return ub;
}

double solve()
{
        double ans = 1e9;
        for (int i = 0; i <= b; i++) {
                double bd = d/(i+1);
                if(attempt(pi/4.,i)) ans = min(ans, sqrt(bd));
                else ans = min(ans, sqrt(bd/sin(2*search(i))));
        }
        return ans;
}

void input()
{
        cin >> d >> n >> b;
        for (int i = 0; i < n; i++)
                cin >> p[i] >> h[i];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        cout << fixed << setprecision(12);
        input();
        cout << solve() << endl;
        return 0;
}

Comments