AOJ 1194: バンパイア / Vampire

整数点ちょうどのところだけ見るのではだめ。

solution

各整数$n \in [-r, +r]$について少しずれた位置$x = n \pm \epsilon \in (-r, +r)$を見ればよい。 そのような点ごとにその位置を太陽が始めて照らす時間を求め、その最小値を答える。 $O( r)$。

implementation

#include <cmath>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

int main() {
    while (true) {
        int r, n; scanf("%d%d", &r, &n);
        if (r == 0 and n == 0) break;
        vector<int> hl(2*r);
        vector<int> hr(2*r);
        repeat (i, n) {
            int xl, xr, hi; scanf("%d%d%d", &xl, &xr, &hi);
            repeat_from (x, max(-r, xl), min(+r, xr)-1+1) setmax(hr[r  +x], hi);
            repeat_from (x, max(-r, xl)+1, min(+r, xr)+1) setmax(hl[r-1+x], hi);
        }
        double t = INFINITY;
        repeat_from (x, -r, +r+1) {
            double y = sqrt(r*r - x*x);
            if (x < +r) setmin(t, r - y + hr[r  +x]);
            if (-r < x) setmin(t, r - y + hl[r-1+x]);
        }
        printf("%.8lf\n", t);
    }
    return 0;
}