AOJ 1194: Vampire
問題
- 与えられたビルの位置から、あと何秒間太陽が隠れているか求めよ
方針
- ビルの位置が整数値なのでビルがある場所についてグリッドを埋めていく
- 太陽が通りうる位置についてグリッドが埋まっていなかったら太陽が通過する瞬間の時間を求める
- 全ての埋まっていないグリッドの中で時間の最小値を求める
コード
#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で挙動が違うという現象に遭遇した
Wandboxでは再現しなかったけど、僕のPCでは本来Segmentation Faultするべきプログラムがcoutすることでエラーなく実行できる謎の現象が確認された。 https://t.co/vcMM9lxfsn
— 川奈 清 (@kivantium) 2016年7月8日AOJのジャッジサーバでも同様の現象が確認できた。
— 川奈 清 (@kivantium) 2016年7月8日
cout版 (https://t.co/FwCOKJqaCh)→AC
printf版 (https://t.co/MFLFVKrSex)→RE