大意：
如上图：坐标轴上有一些点 然后在x轴上安装雷达 告诉你雷达的最大扫描半径 问你最少用多少个雷达就能把所有的点扫描到
分析：
从每个告诉的点都画一个圆，那么它就会和x轴有两个交点 这两个交点之内的任何一个点都能建立雷达扫描的到
我们把两个点之间看做一条线段
那么问题就转化成了 对于x轴上的一些线段 用最少的点覆盖掉
我们只要把 这些线段按右边界按从小到大排序
那么这些线段就是右边界一次增大的了
若一条线段的后面线段的左边界比该边界小 那么就可以通过覆盖这个点来得到
只要一个标记就可以了
代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int maxn = 1005; 9 10 struct Node {11 double x, y;12 }node[maxn], ans[maxn];13 14 double dist(Node n1, Node n2) {15 return sqrt((n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y) );16 }17 18 int eps(double x) {19 if(fabs(x) < 1e-6) {20 return 0;21 } 22 if(x < 0 ) {23 return -1;24 }25 return 1;26 }27 28 bool cmp(Node n1, Node n2) {29 if(eps(n1.y - n2.y) != 0) {30 return n1.y < n2.y;31 } 32 return n1.x < n2.x;33 }34 int vis[maxn];35 36 int main() {37 int n; double r;38 double a, b;39 int t = 1;40 while(scanf("%d %lf",&n, &r) ) {41 if(n == 0 && eps(r) == 0 ) break;42 int cnt = 0;43 for(int i = 0; i < n; i++) {44 scanf("%lf %lf", &a, &b);45 if(eps(r - b) != -1) {46 node[cnt++] = (Node) { a, b };47 }48 }49 for(int i = 0; i < cnt; i++) {50 ans[i].x = node[i].x - sqrt(r * r - node[i].y * node[i].y);51 ans[i].y = node[i].x + sqrt(r * r - node[i].y * node[i].y);52 }53 sort(ans, ans + cnt, cmp);54 int ans_cnt = 0;55 memset(vis, 0, sizeof(vis));56 for(int i = 0; i < cnt; i++) {57 if(vis[i]) continue;58 ans_cnt++;59 for(int j = i + 1; j < cnt; j++) {60 if(vis[j]) continue;61 if(eps(ans[j].x - ans[i].y) != 1) {62 vis[j] = 1;63 }64 }65 vis[i] = 1;66 }67 if(cnt != n) {68 ans_cnt = -1;69 }70 printf("Case %d: %d\n",t++, ans_cnt);71 }72 return 0;73 }