1.1.3

四氧化二磷 · 2018-12-20 20:37:51 · 个人记录

喷水装置

【题目描述】

　　长 L 米，宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。

　　请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？

　　算法：贪心

　　我们先算出每个喷头真正有效的喷水范围S=sqrt(pow(r,2)-pow(w/2,2)),然后以左端点升序排列[若断层则break],每次选择右端点最右边的合法的点。——J(L)X(J)C(H)大佬已经证明其正确性。

#include<bits/stdc++.h>
using namespace std;
struct L{
    double lft,rgt;
    int r,wz;
}a[100010];
bool cmp(L a,L b){return a.lft<b.lft;}
int l,w,n,t;
inline double getlft(int x){double xx=((double)((double)w/2))*((double)((double)w/2));double yy=((double)(a[x].r))*((double)(a[x].r));return (double)((double)a[x].wz-(double)sqrt(yy-xx));}
inline double getrgt(int x){double xx=((double)((double)w/2))*((double)((double)w/2));double yy=((double)(a[x].r))*((double)(a[x].r));return (double)((double)a[x].wz+(double)sqrt(yy-xx));}
int main(){
    scanf("%d",&t);
    while(t--){
        double now=0;int ans=0;
        scanf("%d%d%d",&n,&l,&w);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i].wz,&a[i].r);
            if((double)a[i].r<=(double)((double)w/2)){i--,n--;continue;}
            a[i].lft=getlft(i),a[i].rgt=getrgt(i);
        }
        sort(a+1,a+n+1,cmp);
        if(a[1].lft>0){puts("-1");continue;}
        while(now<l) 
        {
            double m=0;
            for(int i=1;i<=n&&a[i].lft<=now;i++)
            if(a[i].rgt-now>m)m=a[i].rgt-now;
            if(m!=0)ans++,now+=m;else break;
        }
        if(now<w)puts("-1");
        else cout<<ans<<'\n';
    }
    return 0;
}