这题其实蛮简单的，但是呢，主要就是学的地方就是对精度的控制，还有一个贪心的技巧，那个区间覆盖的问题。直接分析代码吧，其中的各种技巧还有需要注意的地方很多。
#include <iostream>#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <
string>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
const double eps = 1e-9;
const double inf = 1e10;
int sgn(
double x) {
return (x > eps) - (x < -eps); //这个地方的主要是浮点数的比较大小的方法eps是控制精度的很小的浮点数
}
int n;
double d;
vector<pair<
double,
double> > rec;
//比较函数，以第二个变量的顺序确定顺序
bool cmp(
const pair<
double,
double> &a,
const pair<
double,
double> &b) {
return a.second < b.second;
}
int main() {
// printf("%lf\n", sqrt(-3.0));
int ca = 0;
while (scanf("%d%lf", &n, &d) == 2) {
if (n == 0 && sgn(d) == 0)
break;
printf("Case %d: ", ++ca);
bool flag =
true;
rec.clear();
for (
int i = 0; i < n; ++i) {
double x, y;
scanf("%lf%lf", &x, &y);
// printf("x: %lf y: %lf\n", x, y);
if (!flag)
continue;
if (sgn(fabs(y) - d) > 0) {
flag =
false;
continue;
}
double len = sqrt(d * d - y * y);
rec.push_back(make_pair(x - len, x + len)); //每个区间的范围
// printf("%lf %lf\n", x - len, x + len);
}
if (!flag) {
printf("-1\n");
continue;
}
sort(rec.begin(), rec.end(), cmp); //排序
int cnt = 0;
double last = -inf;
for (vector<pair<
double,
double> >::iterator it = rec.begin(); it != rec.end(); ++it) {
if (sgn(last - it->first) < 0) { //如果上个区间的最大值比下一个区间的最小值小的话，区间就没有覆盖，这个时候要增加个雷达
++cnt;
last = max(last, it->second); //记录每个区间的那个最大的值
}
}
printf("%d\n", cnt);
}
return 0;
}