- 描述
- 有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。
- 输入
- 第一行输入一个正整数N表示共有n次测试数据。
- 每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
- 随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。
- 输出
- 每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
- 如果不存在一种能够把整个草坪湿润的方案，请输出0。
- 样例输入
2 2 8 6 1 1 4 5 2 10 6 4 5 6 5
- 样例输出
1 2
C代码如下
1 #include "stdio.h" 2 #include "math.h" 3 typedef struct _Equip//区间的结构体 4 { 5 float L; 6 float R; 7 }Equip; 8 9 void Q_sort(Equip **a,int low,int heigh)//对区间按开始端进行升序排序 10 { 11 if(low < heigh) 12 { 13 int i = low,j = heigh; 14 Equip * temp; 15 temp = a[i]; 16 while(i < j) 17 { 18 while(i < j && a[j]->L > temp->L) 19 { 20 j --; 21 } 22 if(i < j) 23 { 24 a[i] = a[j]; 25 i++; 26 } 27 while(i < j && a[i]->L <= temp->L) 28 { 29 i ++; 30 } 31 if(i < j) 32 { 33 a[j] = a[i]; 34 j --; 35 } 36 } 37 a[i] = temp; 38 Q_sort(a,low,i - 1); 39 Q_sort(a,i+1,heigh); 40 } 41 } 42 Equip buf[10000]; 43 Equip *Si[10000]; 44 45 //寻找从begin开始到end-1之间符合条件的一个区间 46 //即开始端 <= Rc 的所有小区间中结束端最大的那个小区间 47 int findmaxR(int begin,int end) 48 { 49 int k = begain; 50 for(int i = begain;i < end;i++) 51 { 52 if(Si[i]->R >= Si[k]->R) 53 { 54 k = i; 55 } 56 } 57 return k; 58 } 59 int main() 60 { 61 int i,j,m,n,count,s; 62 float w,h,Rc,Lc,x,r; 63 while(scanf("%d",&m) != EOF) 64 { 65 for(i = 0;i < m;i++) 66 { 67 scanf("%d%f%f",&n,&w,&h); 68 s = 0; 69 for(j = 0;j < n;j++) 70 { 71 scanf("%f%f",&x,&r); 72 if(r > h/2.0) 73 { 74 buf[j].L =x - sqrt(r * r - h * h / 4.0); 75 if(buf[j].L < 0.0) 76 { 77 buf[j].L = 0.0; 78 } 79 buf[j].R =x + sqrt(r * r - h * h / 4.0); 80 if(buf[j].R > w) 81 { 82 buf[j].R = w; 83 } 84 Si[s++] = &buf[j]; 85 } 86 } 87 Q_sort(Si,0,s-1);//从这里到前边都是准备工作，后边开始贪心了 88 Rc = 0.0; 89 for(j = 0;j < s && Rc < w;) 90 { 91 if(Si[j]->L <= Rc) 92 { 93 int k; 94 for(k = j;k < s;k++) 95 { 96 if(Si[k]->L > Rc) 97 { 98 break; 99 } 100 } 101 int maxR = findmaxR(j,k); 102 count ++; 103 Rc = Si[maxR]->R; 104 j = maxR +1; 105 } 106 else 107 { 108 break; 109 } 110 } 111 if(Rc < w) 112 printf("0\n"); 113 else 114 printf("%d\n",count); 115 } 116 } 117 }
本文转自郝峰波博客园博客，原文链接：http://www.cnblogs.com/fengbohello/archive/2013/01/25/2876233.html，如需转载请自行联系原作者
