首页 > 代码库 > 【kd-tree】CDOJ - 1170 - 红与蓝
【kd-tree】CDOJ - 1170 - 红与蓝
kd-tree模板题,对红点建立kd-tree,用每个蓝点查询,更新最小值即可。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define N 100010 #define EPS 0.00000001 #define INF 1000000000000000007.0 #define KD 2 int qp[KD]; double disn; int n,root; bool dn; double sqr(int x) { return (double)x*(double)x; } int Abs(int x) { return x<0 ? (-x) : x; } struct Node { int minn[KD],maxx[KD],p[KD]; int ch[2]; void Init() { for(int i=0;i<KD;++i) minn[i]=maxx[i]=p[i]; } bool CheckIn() { for(int i=0;i<KD;++i) if(!(minn[i]<=qp[i] && qp[i]<=maxx[i])) return 0; return 1; } int Dis() { if(CheckIn()) return 0; int res=2147483647; res=min(res,Abs(minn[0]-qp[0])); res=min(res,Abs(maxx[0]-qp[0])); res=min(res,Abs(minn[1]-qp[1])); res=min(res,Abs(maxx[1]-qp[1])); return res; } }T[N<<1]; void Update(int rt) { for(int i=0;i<2;++i) if(T[rt].ch[i]) for(int j=0;j<KD;++j) { T[rt].minn[j]=min(T[rt].minn[j],T[T[rt].ch[i]].minn[j]); T[rt].maxx[j]=max(T[rt].maxx[j],T[T[rt].ch[i]].maxx[j]); } } bool operator < (const Node &a,const Node &b) { return a.p[dn]!=b.p[dn] ? a.p[dn]<b.p[dn] : a.p[dn^1]<b.p[dn^1]; } int Buildtree(int l=1,int r=n,bool d=0) { dn=d; int m=(l+r>>1); nth_element(T+l,T+m,T+r+1); T[m].Init(); if(l!=m) T[m].ch[0]=Buildtree(l,m-1,d^1); if(m!=r) T[m].ch[1]=Buildtree(m+1,r,d^1); Update(m); return m; } double Dis(int a[],int b[]) { return sqrt(sqr(a[0]-b[0])+sqr(a[1]-b[1])); } void Query(int rt=root) { disn=min(disn,Dis(T[rt].p,qp)); int dd[2]; for(int i=0;i<2;i++) if(T[rt].ch[i]) dd[i]=T[T[rt].ch[i]].Dis(); else dd[i]=2147483647; bool f=(dd[0]<=dd[1]); if((double)dd[!f]-disn<(-EPS)) Query(T[rt].ch[!f]); if((double)dd[f]-disn<(-EPS)) Query(T[rt].ch[f]); } int main() { // freopen("k.in","r",stdin); // freopen("k.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d%d",&T[i].p[0],&T[i].p[1]); root=(1+n>>1); Buildtree(); disn=INF; for(int i=1;i<=n;++i) { scanf("%d%d",&qp[0],&qp[1]); Query(); } printf("%.3lf\n",disn); return 0; }
【kd-tree】CDOJ - 1170 - 红与蓝
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。