UVa-10382 Watering Grass **

5909 단어 water
/*
* Uva-10382-Watering Grass.cpp
*
   。。( , WA,, , AC , 。。
*
* :
http://apps.hi.baidu.com/share/detail/24628400
*
* Created on: 2011-10-3
* Author:
*/
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxN = 10000 + 5;
const double eps = 1E-7;

int n, l, w;
struct SData{
double x, y;
};
SData interval[maxN];

//
inline int lfcmp(double x){
if (x > -eps) return 1;
else return -1;
}

// X
inline int cmp(const void *a,const void *b){
return lfcmp( (((SData*)a)->x)-(((SData*)b)->x) );
}

// -
void greedy(){
int i = 0, ans = 0, j;
double cover = 0, tmpMax;
bool covered = false;
while(i < n){
j = i;
tmpMax = cover;
while(j<n && lfcmp(cover - (interval[j].x)) > 0){
if(lfcmp((interval[j].y) - tmpMax) > 0)
tmpMax = interval[j].y;
j++;
}
if(i == j) break;

ans++;
cover = tmpMax;
i = j;

if(lfcmp(cover - l) > 0){
covered = true;
break;
}
}
if(covered) printf("%d
", ans);
else printf("-1
");

}


int main(){
while(scanf("%d %d %d", &n, &l, &w) != EOF){
int p[maxN], r[maxN];
for(int i=0; i<n; i++)
scanf("%d %d", &p[i], &r[i]);

for(int i=0; i<n; i++){
//
if(r[i] * 2 < w){
interval[i].x = 0;
interval[i].y = 0;
continue;
}

double d = sqrt((double)r[i]*r[i] - (double)w*w/4);
interval[i].x = p[i] - d;
interval[i].y = p[i] + d;
}

qsort(interval, n, sizeof(SData), cmp);

greedy();
}

return 0;
}

좋은 웹페이지 즐겨찾기