ICPC 国内予選2014C バンパイア AOJ 1194

初心者なので幾何の問題に慣れてなくて焦ったけどかなりすんなりできた。

解説一応しますが説明がすこし面倒なのと解説が必要なほど難しい問題ではないと思うのでかなり簡潔にします

• 建物のx座標の値はありがたいことに整数なので（これが小数だと面倒）x座標で-r～rの範囲内で幅1で切り分けてそれぞれの幅1の領域について考えることにする
• 切り分けた幅1の領域について、どの高さまで建物があるか求める
• 切り分けた幅1の領域内のみについて、太陽がどこまで登ってきても大丈夫か二分探索で調べる
• それぞれの領域についての太陽がのぼれる高さの最小値が答え

参考画像↓

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

double d = 0.00001;
int build[25][3];

int main(){
    int r,n;
    while(true){
        cin >> r >> n;
        if(r + n == 0)break;
        double ans = 100.0;
        for(int i = 0;i < n;i++){ // cin
            for(int j = 0;j < 3;j++){
                cin >> build[i][j];
            }
        }
        for(int x = -r+1;x <= r;x++){
            int hmax = 0;
            for(int i = 0;i < n;i++){
                if(build[i][0] < x && x <= build[i][1]) hmax = max(hmax,build[i][2]);
            }
       //     cout << "x:" << x << ", hmax:" << hmax << endl;
            double a = -30.0,b = (double)hmax,xx;
            if(x <= 0){
                xx = (double) x;
            }else{
                xx = (double) (x-1);
            }
            while(b - a > d){
                double half = (a + b) / 2.0;
                if( (double)r*r > ((double)hmax - half)*((double)hmax - half) + xx*xx){
                    b = half;
                }else{
                    a = half;
                }
            }
            if(ans > a + (double)r) ans = a + (double)r;
        }
        cout << round(ans*10000)/10000 << endl;
    }
}