Space Golf （二分答案）

传送门 ： 点击打开链接

题目超长，基本都是废话， 大概意思就是两点间有几根棒子，可以从左边发射东西，东西落地可以反弹 问恰好落在右端点且不碰到任意一根柱子 最小的速度是多少 中间弹起的次数不能超过b次。

由于b很小，可以直接枚举所有的弹起次数，然后对每一次进行二分答案。后续就是解方程问题了。

#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define MAX 0x3f3f3f3f
#define N 100500
#define mod 1000000007
typedef long long LL;
using namespace std;
const double pi = acos(-1.0);

int n, num;
double d, ans, len;

struct C {
    double h, pos;
} a[20], b[20];

bool ok(double x) {

    double A = 0.25, B = -x, C = len * len;
    double data = B * B - 4 * A * C;
    if(data < 0) return 0;
    double t = sqrt( (-B + sqrt(data)) / (2 * A) );
    double vx = len / t, vy = t / 2;

   // printf("%.2f %.2f\n", vx * vx + vy * vy, x);
    for(int i = 0; i < n; i++) {
        double tt = a[i].pos / vx;
        double hh = vy * tt - 0.5 * tt * tt;
        if(hh < a[i].h) return 0;
    }
    return 1;

}

void solve() {

    double l = 0, r = 100000000000.0;
    for(int i = 0; i < 100; i++) {
        double m = (l+r) / 2;
        if(!ok(m)) l = m;
        else r = m;
    }
    ans = min(ans, sqrt(l));

}

int main()
{
    while(cin >> d >> n >> num) {

        for(int i = 0; i < n; i++) {
            cin >> b[i].pos >> b[i].h;
        }

        ans = 100000000000.0;

        for(int i = 1; i <= num + 1; i++) {

            memcpy(a, b, sizeof(a));
            len = d / i;
            for(int j = 0; j < n; j++) {
                while(a[j].pos > len) {
                    a[j].pos -= len;
                }
                if(a[j].pos > len / 2.0) {
                    a[j].pos = len - a[j].pos;
                }
              //  printf("%.2f ", a[j].pos);
            } 

            solve();

        }

        printf("%.10f\n", ans);

    }

	return 0;
}

Space Golf （二分答案）

原文：http://blog.csdn.net/u013923947/article/details/44568901