首页
登录 | 注册

BZOJ5465 : [APIO 2018] 选圆圈

假设最大的圆半径为$R$,以$2R$为大小将地图划分为一个个格子,那么每个圆只需要检查圆心在附近$9$个格子内部的所有圆。

在当前圆的半径不足$\frac{R}{2}$时重构网格,那么最多重构$O(\log R)$次,且每个圆最多被检查常数次。

时间复杂度$O(n\log n\log R)$,利用Hash可以做到$O(n\log R)$。

 

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=300010,inf=1000000000,BUF=13000000;
int n,m,i,x,y,q[N],ans[N],size;char Buf[BUF],*buf=Buf;
struct E{int x,y,r;E(){}E(int _x,int _y,int _r){x=_x,y=_y,r=_r;}}e[N],f[N];
vector<int>g[N],tmp;
inline void read(int&a){int f=0;for(a=0;*buf<45;buf++);if(*buf==45)f=1,buf++;while(*buf>47)a=a*10+*buf++-48;if(f)a=-a;}
inline bool cmp(int x,int y){
  if(e[x].r!=e[y].r)return e[x].r>e[y].r;
  return x<y;
}
inline bool cmpe(const E&a,const E&b){
  if(a.x!=b.x)return a.x<b.x;
  return a.y<b.y;
}
inline void init(int _){
  if(size&&size/2<_)return;
  size=_;
  int i,j,k,cnt;
  m=0;
  for(i=1;i<=n;i++)if(!ans[i]){
    int x=e[i].x/size,y=e[i].y/size;
    f[++m]=E(x,y,i);
  }
  sort(f+1,f+m+1,cmpe);
  cnt=0;
  for(i=1;i<=m;i=j){
    for(j=i;j<=m&&f[i].x==f[j].x&&f[i].y==f[j].y;j++);
    f[++cnt]=f[i];
    g[cnt].clear();
    for(k=i;k<j;k++)g[cnt].push_back(f[k].r);
  }
  m=cnt;
}
inline int ask(int x,int y){
  int l=1,r=m,mid;
  while(l<=r){
    mid=(l+r)>>1;
    if(f[mid].x==x&&f[mid].y==y)return mid;
    if(f[mid].x<x||f[mid].x==x&&f[mid].y<y)l=mid+1;else r=mid-1;
  }
  return 0;
}
inline bool check(int i,int j){return 1LL*(e[i].r+e[j].r)*(e[i].r+e[j].r)>=1LL*(e[i].x-e[j].x)*(e[i].x-e[j].x)+1LL*(e[i].y-e[j].y)*(e[i].y-e[j].y);}
inline void apply(int S){
  if(ans[S])return;
  init(e[S].r*2);
  int x=e[S].x/size,y=e[S].y/size,i,j,k,o,t;
  for(i=x-1;i<=x+1;i++)for(j=y-1;j<=y+1;j++)if(i>=0&&j>=0){
    o=ask(i,j);
    if(!o||!g[o].size())continue;
    tmp.clear();
    for(k=0;k<g[o].size();k++){
      t=g[o][k];
      if(check(S,t))ans[t]=S;else tmp.push_back(t);
    }
    swap(g[o],tmp);
  }
}
int main(){
  fread(Buf,1,BUF,stdin);read(n);
  for(i=1;i<=n;i++){
    read(x),read(y),read(e[i].r);
    e[i].x=x+inf;
    e[i].y=y+inf;
    q[i]=i;
  }
  sort(q+1,q+n+1,cmp);
  for(i=1;i<=n;i++)apply(q[i]);
  for(i=1;i<=n;i++)printf("%d%c",ans[i],i<n?' ':'\n');
  return 0;
}

  


相关文章

  • PyCharm 2018 永久激活
    PyCharm是一种Python IDE,带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具,比如调试.语法高亮.Project管理.代码跳转.智能提示.自动完成.单元测试.版本控制.此外,该IDE提供了一些高级功能,以用于 ...
  • LSTM实现中文文本情感分析
    1. 背景介绍 文本情感分析是在文本分析领域的典型任务,实用价值很高.本模型是第一个上手实现的深度学习模型,目的是对深度学习做一个初步的了解,并入门深度学习在文本分析领域的应用.在进行模型的上手实现之前,已学习了吴恩达的机器学习和深度学习的 ...
  • ERP不规范,同事两行泪
    最近的很多次对外交流,都聊到了ERP建设的话题,并且无一例外的不那么让人省心,回想我这么多年走过的ERP坑坑路,在这里也写下经验和总结,希望能给正在或者即将走上ERP建设路的企业一些思考和帮助. 导读 1.几个瞎眼而普遍的案例 2.ERP的 ...
  • 汝之蜜糖,吾之砒霜——聊聊软件开发中的最佳实践
        "描述一个事物,唯有一个名词定义它的概念,唯有一个动词揭露它的行为,唯有一个形容词表现它的特征.要做的,就是用心去寻找那个名词.那个动词.那个形容词--" -- 福楼拜 (Gustave Flaubert)   ...
  • 为什么说 Java 程序员到了必须掌握 Spring Boot 的时候?
    Spring Boot 2.0 的推出又激起了一阵学习 Spring Boot 热,就单从我个人的博客的访问量大幅增加就可以感受到大家对学习 Spring Boot 的热情,那么在这么多人热衷于学习 Spring Boot 之时,我自己也在 ...
  • 如何零基础开始自学Python编程
    转载——原作者:赛门喵 链接:https://www.zhihu.com/question/29138020/answer/141170242 0. 明确目标 我是真正零基础开始学Python的,从一开始的一窍不通,到3个月后成功搭建了一个 ...

2020 cecdns.com webmaster#cecdns.com
12 q. 0.080 s.
京ICP备10005923号