UVA 10382 Watering Grass（区间覆盖）

n sprinklers are installed in a horizontal strip of grass l meters long and w meters wide. Each sprinkler is installed at the horizontal center line of the strip. For each sprinkler we are given its position as the distance from the left end of the center line and its radius of operation. What is the minimum number of sprinklers to turn on in order to water the entire strip of grass?

Input

Input consists of a number of cases. The first line for each case contains integer numbers n, l and w with n ≤ 10000. The next n lines contain two integers giving the position of a sprinkler and its radius of operation. (The picture above illustrates the first case from the sample input.)

Output

For each test case output the minimum number of sprinklers needed to water the entire strip of grass. If it is impossible to water the entire strip output ‘-1’.

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

-1

题目链接

题意

一块长l宽w的草坪，中心线有n个喷水装置，处于位置p，覆盖半径为r的区域。请选择尽量少的喷水装置，将整个草坪覆盖。

思路

考虑每个喷水器对草坪的实际影响，实质上是圆与草坪相交组成的矩形区间，那么这个问题就转换成了区间覆盖。

先预处理，无法覆盖草坪的区间除去。小区间显然不应该考虑。初始起点为0，对于每个起点s，都取能覆盖它的最长的区间（按终点从大到小排序），并更新起点，循环这样的操作，直到覆盖了整个草坪。注意，这里需要double，r*r会爆int，实测。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include <queue>

#include <vector>

#include<bitset>

#include<map>

#include<deque>

using namespace std;

typedef long long LL;

const int maxn = 1e4+;

const int mod = +;

typedef pair<int,int> pii;

#define X first

#define Y second

#define pb push_back

//#define mp make_pair

#define ms(a,b) memset(a,b,sizeof(a))

const int inf = 0x3f3f3f3f;

#define lson l,m,2*rt

#define rson m+1,r,2*rt+1

typedef long long ll;

#define N 1000010

struct node {

    double a,b;

}square[];

int cmp(node x,node y){

    return x.b>y.b;

}

int main(){

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif // LOCAL

    int n;

    double l,w;

    double r,p;

    while(~scanf("%d%lf%lf",&n,&l,&w)){

        int tot=;

        for(int i=;i<n;i++){

            scanf("%lf%lf",&p,&r);

            if(r<=w/) continue;

            square[tot].a=p-sqrt(r*r-w*w/);

            square[tot++].b=p+sqrt(r*r-w*w/);

        }

        sort(square,square+tot,cmp);

        double st=;

        int ans=;

        while(st<l){

            int i;

            for(i=;i<tot;i++){

                if(square[i].a<=st && square[i].b>st){

                    st=square[i].b;

                    ans++;

                    break;

                }

            }

            if(i==tot) break;

        }

        if(st<l){

            puts("-1");

        }else{

            printf("%d\n",ans);

        }

    }

    return ;

}

巴特西

UVA 10382 Watering Grass（区间覆盖）

最新文章

热门文章