AOJ 1194: Vampire

問題

Vampire | Aizu Online Judge

  • 与えられたビルの位置から、あと何秒間太陽が隠れているか求めよ

方針

  • ビルの位置が整数値なのでビルがある場所についてグリッドを埋めていく
  • 太陽が通りうる位置についてグリッドが埋まっていなかったら太陽が通過する瞬間の時間を求める
  • 全ての埋まっていないグリッドの中で時間の最小値を求める

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
  
int s[21][41];
int main(void){
    int r, n, xl, xr, h;
    while(cin >> r >> n && r) {
        rep(i, 21) rep(j, 41) s[i][j] = 0;
        rep(i, n) {
            cin >> xl >> xr >> h;
            for(int y=0; y<h; ++y) {
                for(int x=xl+20; x<xr+20; ++x) {
                    s[y][x] = 1;
                }
            }
        }
        double mint = numeric_limits<double>::max();
        rep(y, 21) {
            for(int x=-r+20; x<r+20; ++x) {
                if(s[y][x] == 0) {
                    double t;
                    if(x<20) t = (double) y+r-sqrt(pow((double)r,2.0)-pow(x-19.0, 2.0));
                    else t = (double) y+r-sqrt(pow((double)r,2.0)-pow(x-20.0, 2.0));
                    mint = min(mint, t);
                }
            }
        }
        printf("%.4lf\n", mint);
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1905757

反省

  • 検索すると2分探索で決めるという解法があり、そのほうが一般的に使える解法だと思った
  • たまたま間違えて配列外アクセスしたら、coutとprintfで挙動が違うという現象に遭遇した