首页 > 其他 > 详细

Radar Installation

时间:2019-07-20 15:12:48      阅读:101      评论:0      收藏:0      [点我收藏+]

Radar Installation

在平面直角坐标系中,给出n个点,都在x轴上方,记第i个点为\((x_i,y_i)\),现在请求出在x轴寻找尽可能少的点数数目作为圆心,以r为半径的圆,能够覆盖所有的点,\(n\leq 1000\)

此题直接做不好做,重在转换模型,现在转换为我们最熟悉的区间问题,于是发现对于一个点A\((x,y)\),能够覆盖它的点B\((l,0)\)作为圆心,到达极限时,也就是\(AB=r\)之时,于是可以列出方程

\[\sqrt[2]{(x-l)^2+(y-0)^2}=r\]

也就是

\[(x-l)^2+y^2=r^2\]

就是

\[(x-l)^2=r^2-y^2\]

\[x-l=\pm\sqrt[2]{r^2-y^2}\]

...

\[x=l\pm\sqrt[2]{r^2-y^2}\]

容易发现,当\(r^2<y^2\)时,就不存在圆B可以覆盖点A了,这个要特判,发现了马上输出无解。

于是对于任意一个点i,而言当且仅当圆心B\((l,0)\),\(l\in[l-\sqrt[2]{r^2-y^2},l+\sqrt[2]{r^2-y^2}]\)时,圆B能够覆盖i。

处理出这个,于是问题转化为有n个区间,用最少的点被所有区间包含的点的数目,这是一个区间问题,记第i个区间为\([l_i,r_i]\),我们首要考虑排序。

不妨按左端点排序,现在对于其中一个区间i考虑,它被那些点包含,设\(j\)为用的最后一个点所在位置,如果\(j< l_i\),显然i不可能包含原来已经有的点,因此只能新开一个点,令\(j=r_i\),如果\(l_i\leq j\),那么令\(j=\min(r_i,j)\)

正确性:显然新开一个是正确的,对于用原来的\(j=\min(r_i,j)\)来说,因为我们是按左端点排序,那么对于前面的区间包含j的区间讲,它的左端点必然小于i的左端点,而对于它们的右端点必然有大于j,现在j变小了,自然不可能超出它们的右端点,而\(r_i\geq l_i\),所以在小不会小过\(l_i\),自然也不会小过前面的区间,于是我们证明的这样操作不会使原来的包含关系改变。

但是并不能证明不开比新开优秀,这就是微扰法捉襟见肘的地方了,于是考虑决策包容,对于开一个新的点,它所在的选择范围必然是在第i个区间所包含的点内,但是不开一个新的区间,以后开一个新的区间,又和它同等优秀,但是选择范围可以达到任意实数,所以后者包含前者,自然后者会更加优秀。

得证。

于是总上所素,我们只需要把点转化为区间,再把区间按照左端点排序,然后记录最后一个已经开的点所在坐标i,如果对于第i区间\([l_i,r_i]\)满足\(l_i\leq j\),就令\(j=\min(j,r_i)\),否则就新开一个点,令\(j=r_i\)
时间复杂度显然\(O(n)\)

参考代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define il inline
#define ri register
#define ll long long
#define Size 1500
using namespace std;
struct inter{
    double l,r;
    il bool operator<(const inter&x)const{
        return l<x.l;
    }
}I[Size];
il void read(int&);
template<class free>
il free Min(free,free);
int main(){
    int n,d,ans(0);
    read(n),read(d);
    for(int i(1),x,y;i<=n;++i){
        read(x),read(y);
        if(d*d-y*y<0)return puts("-1"),0;
        I[i].l=x-sqrt((ll)d*d-(ll)y*y);
        I[i].r=x+sqrt((ll)d*d-(ll)y*y);
    }sort(I+1,I+n+1);double gzy(-1e16);
    for(int i(1);i<=n;++i)
        if(I[i].l<=gzy)gzy=Min(gzy,I[i].r);
        else ++ans,gzy=I[i].r;printf("%d",ans);
    return 0;
}
template<class free>
il free Min(free a,free b){
    return a<b?a:b;
}
il void read(int &x){
    x^=x;ri char c;while(c=getchar(),c==' '||c=='\n'||c=='\r');
    ri bool check(false);if(c=='-')check|=true,c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(check)x=-x;
}

Radar Installation

原文:https://www.cnblogs.com/a1b3c7d9/p/11217188.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!