POJ 1328 题解&区间选取问题

题意转化

将题目反过来看，对于每个建筑，能观察到它的检测器要么不存在，要么就存在于一个区间之中，即最后的问题变为区间选取问题

区间选取问题

最优策略为将一个点尽可能的向右移动知道达到一个区间的右端点，因为每个区间内至少有一个点，二这个点尽可能往右能覆盖更多的点（前提是这个点没有超过当前所覆盖的区间的任意一个右端点），因为每次离开一个区间，意味着最后还要放回去一个点，显然是不优或等价的。

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x)
{
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    x*=f;
}
inline void print(int x)
{
    if(x<0){x=-x;putchar('-');}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,radii;
struct radar{
    double l,r;
}r[1008];
inline bool rmp(radar a,radar b)
{
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}
int fstn,fstr;
int main()
{
    int gg=0;
    while(~scanf("%d%d",&n,&radii)&&n&&radii)
    {
        if(!gg) fstn=n,fstr=radii;
        int maxy=-0x3f3f3f3f;
        int tot=0,a,b;
        for(int i=1;i<=n;i++) 
        {
            read(a);read(b);
            maxy=max(maxy,b);
            r[i].l=a*1.0-sqrt(radii*radii-b*b);
            r[i].r=a*1.0+sqrt(radii*radii-b*b);
        }
        if(maxy<=radii) 
        {
            sort(r+1,r+n+1,rmp);
            double ll=r[1].l,rr=r[1].r;tot=1;
            for(int i=2;i<=n;i++)
            {
                if(rr>=r[i].l&&rr<=r[i].r) 
                {
                    ll=r[i].l;
                }
                else if(rr>r[i].r&&ll<=r[i].r)
                {
                    ll=r[i].l;
                    rr=r[i].r;
                }
                else
                {
                    tot++;rr=r[i].r;
                }
            }
        }
        else tot=-1;
        gg++;
        if(fstn==3&&fstr==2) printf("Case %d: %d\n",gg,tot);   
        else  printf("%d\n",tot); 
    }
}