UVA - 10382- Watering Grass
uva 10382 - Watering Grass(区域覆盖问题)
Sample Input
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1
Sample Output
6
2
-1
题目大意:
有一块草坪,长为l,宽为w,在它的水平中心线上有n个位置可以安装喷水装置,各个位置上的喷水装置的覆盖范围为以它们自己的半径ri为圆。求出最少需要的喷水装置个数。
分析与总结:
这题的关键在于转化
根据这图可以看出,一个喷水装置的有效覆盖范围就是圆中间的那个矩形。所以,在输入的同时,进行预处理,转换成矩形左边的坐标和右边的坐标。这样,其实就转换成了经典的区间覆盖问题。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stdio.h>
using namespace std;
int n,nIndex;//数据个数、结构体参数
double l,w;//草坪长、宽
struct Node//结构体输入
{
double left;
double right;
}arr[10008];//洒水范围left到right
int cmp(Node a,Node b)
{
return a.left < b.left;
}
int main()
{
double p,r;//洒水坐标、半径
while(scanf("%d%lf%lf",&n,&l,&w)!=EOF)
{
int i,j;
nIndex=0;
for(i=0; i<n; ++i)
{
scanf("%lf%lf",&p,&r);
if(w/2>=r)
continue; //直径小于宽度的不考虑
double t=sqrt(r*r-w*w/4.0);
arr[nIndex].left=p-t;
arr[nIndex].right=p+t;
nIndex++;
}
sort(arr,arr+nIndex,cmp);
int sum=0;
double left=0, right=0;
int flag=0;
if(arr[0].left <= 0 )
{
i=0;
while(i < nIndex)
{
j=i;
while(j<nIndex && left>=arr[j].left)
{
if(arr[j].right > right)
right=arr[j].right;
j++;
}//取大范围的长方形
if(j==i)
break;//如果上面的循环体没有执行,说明之后都没有满足的了
sum++;
left=right;
i=j;
if(left>=l)
{
flag=1;
break;
}
}
}
if(flag) printf("%d\n",sum);
else printf("-1\n");
}
return 0;
}