雷达安装
以岛屿为圆心，雷达范围为半径，计算此圆与x轴交点的线段，以此把所有岛屿的区间计算出来。
因此，这道题就变成了在数轴上选最少的点，覆盖给定线段。
把每条线段以右端点排序，然后进行选择即可。
sqrt函数使用时要保证数据类型一致。
注意输出格式以及Case的C要大写= =
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct radarRange {
double left;
double right;
bool operator < (const radarRange &x) const //<重载，用于sort函数
{
if (right != x.right) return right < x.right;
return left < x.left;
}
};
struct islandPosition {
int x;
int y;
};
int radar()
{
int n, d;
cin >> n >> d;
if (n == 0 && d == 0)
return -2;
islandPosition *p = new islandPosition[n];
radarRange *r = new radarRange[n];
for (int i = 0; i < n; i++)
{
cin >> p[i].x >> p[i].y;
}
if (d == 0)
return -1;
for (int i = 0; i < n; i++)
if (p[i].y > d)
{
return -1;
}
for (int i = 0; i < n; i++)//计算雷达安装范围
{
double tmp = sqrt(double(d *d) - double(p[i].y * p[i].y));
r[i].left = p[i].x - tmp;
r[i].right = p[i].x + tmp;
}
//for (int i = 0; i < n; i++)//debug
//{
// cout << r[i].left << ' ' << r[i].right << endl;
//}
sort(r, r + n);
//for (int i = 0; i < n; i++)//debug
//{
// cout << r[i].left << ' ' << r[i].right << endl;
//}
double start, end;
int sum = 1;
start = r[0].left;
end = r[0].right;
for (int i = 1; i < n; i++)//计算所需雷达数
{
if (r[i].left <= end && r[i].left >= start)
{
start = r[i].left;
}
/*if (r[i].left <= end && r[i].left < start)
{
;
}*/
if (r[i].left > end)
{
start = r[i].left;
end = r[i].right;
sum++;
}
}
delete[] p; delete[] r;
return sum;
}
int main()
{
int tmp;
int sum = 1;
while (1)
{
tmp = radar();
if (tmp == -2) break;
cout << "Case " << sum++ << ": " << tmp << endl;
}
system("pause");
}
/*
Sample Input
3 2
1 2
-3 1
2 1
1 2
0 2
0 0
Sample Output
Case 1: 2
Case 2: 1
*/
