範例程式碼 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[\ݭYpa׫h̳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;
}