#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
int N, D;
const int MAX_N = 1000;
typedef pair<int, int> P;
typedef pair<double, double> ps;
bool comp(P p1, P p2) {
	return p1.first < p2.first;
}
P p[MAX_N];
int counts = 1;
void greedy() {
	int no = 0;
	sort(p, p + N, comp);
	for (int i = 0; i < N; i++) {
		if (p[i].second > D) {
			cout << "Case " << counts << ": " << -1 << endl;
			counts++;
			return;
		}
	}
	ps radar[MAX_N];
	for (int i = 0; i < N; i++) {
		double temp = sqrt((double)(D*D - p[i].second*p[i].second));
		double right_bound = temp + p[i].first;
		double left_bound = -temp + p[i].first;
		radar[i].first = left_bound;
		radar[i].second = right_bound;
		
	}
	sort(radar, radar + N, comp);
	
	for (int i = 0; i < N; i++) {
		no = no + 1;
		double xx = radar[i].second;
		for (int j = i+1; j < N; j++) {
			if (radar[j].first<=xx) {
				if (radar[j].second < xx)
					xx = radar[j].second;
				i = i+1;
			}
			else {
				break;
			}

		}
	}
	cout <<"Case "<<counts<<": "<< no << endl;
	counts++;
}
int main() {
	while (true)
	{
		
		cin >> N >> D;
		if (N == 0) {
			break;
		}
		memset(p, 0, sizeof(p));
		for (int i = 0; i < N; i++) {
			cin >> p[i].first >> p[i].second;
		}
		
		greedy();
	}
	system("pause");
	return 0;
}

• Re:分享一下我的代码，贪心算法，同样是以岛屿为圆心画圆 (1510) 961592690 2018-10-18 15:50:53