H - 和平精英（二分+并查集）-白红宇的个人博客

H - 和平精英（二分+并查集）

发布日期：2021-05-07 02:27:42 浏览次数：20 分类：精选文章

本文共 1713 字，大约阅读时间需要 5 分钟。

1.很经典的一道题，之前做过类似的一道题，这个题只是判断条件多了几个，但是做法都一样

2.首先要满足圆的半径尽量大，因为这样才可以覆盖的范围更大以至于敌人无法通过，然后答案又要求最小，肯定想到二分圆的半径了

3.然后我们知道，当圆与圆至少有一个交点时，那么中间是无法通过的，不难想到这时的圆与圆形成了若干个连通块，那么考虑这些连通块，我们只需

求出连通块的上下左右边界，然后判断是否形成如下四种情况之一：

时间复杂度 $O(n^2logk),k$ 为常数

#include 
   
    #include 
    #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define lowbit(x) (x&(-x))#define mkp(x,y) make_pair(x,y)#define mem(a,x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair
                
                  P;const double eps=1e-8;const double pi=acos(-1.0);const int inf=0x3f3f3f3f;const ll INF=1e18;const int Mod=1e9+7;const int maxn=2e5+10;int n,xx,yy;int father[105];ll x[105],y[105];double dx[105][105];double u[105],d[105],L[105],R[105];double dis(ll x1,ll y1,ll x2,ll y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}int Find(int x){ return father[x]==x?x:father[x]=Find(father[x]);}bool check(double m){ for(int i=1;i<=n;i++){ u[i]=y[i]+m; d[i]=y[i]-m; L[i]=x[i]-m; R[i]=x[i]+m; father[i]=i; for(int j=1;j
                 
                  =dx[i][j]){ int fi=Find(i),fj=Find(j); father[fi]=fj; u[fi]=max(u[fj],u[fi]); d[fj]=min(d[fj],d[fi]); L[fj]=min(L[fj],L[fi]); R[fj]=max(R[fj],R[fi]); } } } for(int i=1;i<=n;i++) if( (u[i]>=yy && d[i]<=0) || (L[i]<=0 && R[i]>=xx) || (L[i]<=0 && d[i]<=0) || (R[i]>=xx && u[i]>=yy) ) return 1; return 0;}int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>xx>>yy; for(int i=1;i<=n;i++){ cin>>x[i]>>y[i]; for(int j=1;j

上一篇：华为杯中国地质大学(武汉)第十七届ICPC程序设计大赛暨华中地区部分高校第十五届ICPC邀请赛

下一篇：B - 卡牌对战游戏（动态RMQ）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章