範例程式碼 uva10382
//uva10382
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
struct segment {
double leftEnd, rightEnd;
};
int cmp(segment a, segment b) {
return a.leftEnd < b.leftEnd;
}
segment sprinter[10005];
int main() {
int n, l, w; // xƥ n ,aBe: l,w
while(scanf("%d %d %d", &n, &l, &w) == 3) {
double sp, sr; // xmBMxb|
int esNum = 0;
for(int i = 0; i < n; i++) {
scanf("%lf %lf", &sp, &sr); //ŪJxmMxb|
if(2 * sr <= w)
continue; //pGx|paeסBxp]л\s
double eLength = sqrt(sr * sr - w * w / 4.0);
sprinter[esNum].leftEnd = sp - eLength;
sprinter[esNum++].rightEnd = sp + eLength; //xл\uqBkI
}
sort(sprinter, sprinter + esNum, cmp);
int ans = 0, flag = 0;
if(sprinter[0].leftEnd > 0) {
printf("-1\n"); //䥼[\BL,X-1
continue;
}
double coveredLeftEnd = 0, coveredRightEnd = 0;
int sl = 0;
while(coveredLeftEnd < l) { //w[\ݭYpah̳gkѥNx}CѥkܯNл\̦hxçsw[\Bk
for(int i = sl; i < esNum; i++) {
if(sprinter[i].leftEnd <= coveredLeftEnd && sprinter[i].rightEnd > coveredRightEnd) {
coveredRightEnd = sprinter[i].rightEnd;
sl = i;
}
}
if(coveredLeftEnd == coveredRightEnd) {
flag = 1;
break;
}
coveredLeftEnd = coveredRightEnd;
ans++;
}
if(!flag)
printf("%d\n", ans);
else
printf("-1\n");
}
return 0;
}