异想天开

What's the true meaning of light, Could you tell me why

喷水装置(二)

日期:2015-06-04 10:13:22
  
最后更新日期:2015-06-04 10:13:22
描述
有一块草坪,横向长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
解析:
贪心准则就是,每次选择一个能覆盖左边的起始位置的右边界最远的喷水装置。

将喷水装置转换为区间覆盖,首先将区间排序,排序规则:
1.左边界从小到大排序
2.左边届相等,按右边届从大到小排序
排序后的集合: SI={[a1,b1],[a2,b2],[a3,b3]...}

算法,初始状态:已排序集合SI,left=0:
1.SI集合是否存在左边界小于或等于left的区间,若存在go 2,不存在go 3
2.在这些左边届小于或等于left的区间中,选择右边界最大的区间,更新left等于该区间的最大右边界,若left大于或草坪长度,go 4,否则go 1
3.该情况,不能完全覆盖,退出
4.完全覆盖,退出


[code lang="cpp"]
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node{
double l,r; //区域的左右边界
};
const int N=10001;
struct node data[N];

const double INF=0.000001;
int cmp(void *a,void *b){
struct node *pa=(struct node*)a;
struct node *pb=(struct node*)b;
if (pa->l-pb->l<-INF){
return -1;
}
if (pa->l-pb->l>INF){
return 1;
}
if (pa->r-pb->r>INF){
return -1;
}
//开始没加下面这句
if (pa->r-pb->r<-INF){
return 1;
}
return 0;
}

int solve(){
int t;
scanf("%d",&t);
while (t--){
int w,h,n;
scanf("%d %d %d",&n,&w,&h);
int j=0;
for (int i=0; i<n; ++i){
int xi,ri;
double l=0.0,r=0.0;
scanf("%d %d",&xi,&ri);
r=(double)ri;
if (r-((double)h/2)>INF){
r=sqrt(r*r-((double)(h*h))/4);
if (xi-r>INF){
l=xi-r;
}
data[j].l=l;
data[j].r=xi+r;
++j;
}
}
n=j;
qsort(&data[0],n,sizeof(struct node),(__compar_fn_t )cmp);
/*for (int i=0; i<n; ++i){
printf("%f %f\n",data[i].l,data[i].r);
}*/

double left=0.0,max=(double)w;
int min=0;
for (int i=0; i<n; ){
double tmp=0.0;
for (; i<n; ++i){
if (data[i].l-left<-INF || fabs(data[i].l-left)<INF){
if (data[i].r-left>INF){
if (data[i].r-tmp>INF){
tmp=data[i].r;
}
}
} else {
break;
}
}
if ( tmp-left <-INF || fabs(tmp-left)<INF ){
break;
}
left = tmp;
min++;
if (fabs(left-max)<INF || left-max>INF){
break;
}
}
if (left-max<-INF){
printf("0\n");
} else {
printf("%d\n",min);
}
}
return 0;
}

int main()
{
solve();
return 0;
}
[/code]