UVA 10382 Watering Grass ( 區間覆蓋問題 )

UVa Online Judge
用畢氏定理把輸入轉換成單純的區間覆蓋問題就可以了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 4;

int n;
double l, w;
double x[MAXN], r[MAXN];

typedef pair<double, double> pdd;
pdd p[MAXN];
void solve(){
    int m = 0;
    w /= 2.0;
    for(int i = 0; i < n; ++i){
        if( r[i] < w ) continue;
        double range = sqrt( r[i] * r[i] - w * w );
        p[ m++ ] = pdd( x[ i ] - range, x[ i ] + range );
    }
    sort( p, p + m );
    int rb = 0, cnt = 0;
    double pos = 0.0;
    while( pos < l ){
        int best_idx = -1;
        while( rb < m && p[ rb ].first <= pos ){
            if( best_idx < 0 || p[ rb ].second > p[ best_idx ].second )
                best_idx = rb;
            ++rb;
        }
        if( best_idx < 0 ) break;
        ++cnt;
        pos = p[ best_idx ].second;
    }
    if( pos < l ) puts("-1");
    else printf("%d\n", cnt);
}

int main(){
    while( scanf("%d%lf%lf", &n, &l, &w) == 3 ){
        for(int i = 0; i < n; ++i)
            scanf("%lf%lf", &x[i], &r[i]);
        solve();
    }
    return 0;
}