MYF

UVa 10382 Watering Grass

Posted on | In | | Visitors

题目链接

UVa 10382

方法：贪心

题目分析

题目大意

给定n个喷灌机，以及草坪的长l、宽w，以及每个喷灌机的所在位置o和覆盖半径r，要求草坪所有地方都喷到水，求最少需要几个喷灌机。

解析

先用初中学的垂径定理算该喷灌机可覆盖的范围，记录下l和r，储存在一个segment里，将这些segment线段按左端点排序。每次找未覆盖区域(用left和right表示两端)中，左端点大于等于left的线段，并且找到这些线段中右端点的最大值，更新right。这么着循环一次，则表示多用一个喷灌机，ans＋＝1。输出－1的话有两种情况，第一种，一开始就找不到能覆盖左端点的喷灌机，第二种，没有办法移步到下一个喷灌机。(其实本质上来讲是一种)

代码

参考题解：http://blog.csdn.net/shuangde800/article/details/7828675

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug         printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
int n,ans,sCnt;
double o,r,l,w;
bool flag;
struct segment{
    double l,r;
}s[maxn];
bool cmp(segment a,segment b){
    return a.l<b.l;
}
int main(){
    while (scanf("%d%lf%lf",&n,&l,&w)!=EOF) {
        flag=false;
        ans=sCnt=0;
        for (int i=0; i<n; i++) {
            scanf("%lf%lf",&o,&r);
            if(w/2>=r) continue; //坑
            double tmp=sqrt(r*r-w*w/4.0);
            s[sCnt].l=o-tmp;
            s[sCnt++].r=o+tmp;
        }
        
        sort(s, s+sCnt, cmp);
        
        if (s[0].l>0) {
            printf("-1\n");
            continue;
        }
        
        int index=0;
        double left=0,right=0;
        while (index<sCnt) {
            int tmp=index;
            
            while (tmp<sCnt&&s[tmp].l<=left)
                right=max(right, s[tmp++].r);
            if (tmp==index) break;//表示上面的while循环未执行，没有符合条件的
            
            ans++;
            index=tmp;//记录已选择的最后一个喷灌机的下标
            left=right;//右端点作为左端点，找从新的left开始的区间
            if (left>=l) {
                flag=true;
                break;
            }
        }
        
        if (flag) cout<<ans<<endl;
        else cout<<-1<<endl;
    }
}