注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

JZPFAR 内含k-d tree  

2013-05-28 17:26:34|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题的意义就是k-d tree的入门题吧
在这里讲讲k-d tree是什么
k-d tree,k维的树。所以这道题我们还可以叫他叫2-d tree
他的构造方法是什么呢?
以2-d tree为例,因为k-d tree差不多
正确构造方法:对于[l,r]这段区间我们建2-d tree,先看他们x的方差,再看y的方差,根据x,y的方差大小选择用哪一维划分。不妨设x的方差更小,我们找到[l,r]这段区间的x的中位数(可以用 nth_element 函数实现),丢到p节点,然后把[l,mid-1]建成一棵子树变成p的左儿子,[mid+1,r]建成一棵子树变成p的右儿子,这是用递归建立的。有的时候还可以维护一下子树的x的最大最小值,y的最大最小值,就相当于是这棵子树的点所构成的一个矩形了。
然后是查询,比如我们要查离某个点最近的点,从根节点出发,如果在左儿子当然要试试左儿子吗;同时回溯的时候看看,如果以查询点为圆心,当前答案为半径,与右儿子的子树代表的矩形有交,我们就再走右儿子看看。
我觉得吧,如果没有后面的回溯,很显然是log n的查询。但是有了后面那个,时间复杂度就算不清了。vfleaking 说是 sqrt(n)的,这是多么多么的不可思议不可理喻啊
k近点的话用个priority_queue来搞,其他部分类似最近点
最远点的话和最近点反一反,在左儿子就往右儿子走
k远点的话就是最远点与k近点的结合
还有个值得一提的事情就是说,虽然标准写法是根据方差来看,但是有位叫“谢图图”的大神说按k为循环一维一维顺序搞也可以,卡不掉。比如3-d tree,我就先按x划分,再按y划分,再按z划分
http://xietutu.com/archives/782
这是谢图图大神的博客……
最后问一句:“谢图图大神是谁啊??”

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define it tree[root]
#define lson tree[root<<1]
#define rson tree[root<<1|1]
#define maxn 100010
typedef long long LL;
int flag;
bool use[maxn*4];
template<class T>
void Read(T &digit)
{
digit=0;
char c;
for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
bool type=true;
if(c=='-')
type=false,c=getchar();
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
if(type==false)
digit=-digit;
}
struct Point
{
int id;
LL x,y;
friend bool operator < (const Point &a,const Point &b)
{
if(flag==0)
return a.x<b.x;
return a.y<b.y;
}
}p[maxn];
LL Len(const Point &a,const Point &b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
struct Node
{
LL dis;
int id;
Node() {}
Node(LL dis,int id): dis(dis),id(id) {}
friend bool operator < (const Node &a,const Node &b)
{
return a.dis>b.dis||(a.dis==b.dis&&a.id<b.id);
}
};
std::priority_queue<Node> Q;
struct msgnode
{
LL min[2],max[2];
/*
min[0]表示x最小值,min[1]表示y最小值
max[0]表示x最大值,max[1]表示y最大值
*/
LL dis(const Point &p)
{
LL x=std::max(abs(p.x-min[0]),abs(p.x-max[0]));
LL y=std::max(abs(p.y-min[1]),abs(p.y-max[1]));
return x*x+y*y;
}
friend msgnode operator + (const msgnode &a,const msgnode &b)
{
msgnode c;
c.min[0]=std::min(a.min[0],b.min[0]);
c.min[1]=std::min(a.min[1],b.min[1]);
c.max[0]=std::max(a.max[0],b.max[0]);
c.max[1]=std::max(a.max[1],b.max[1]);
return c;
}
};
struct kdTree
{
Point p;
msgnode msg;
}tree[maxn*4];
int n,m;
void Build(int root,int l,int r,int k)
{
if(l>r)
return ;
use[root]=true;
flag=k;
int mid=(l+r)>>1;
std::nth_element(p+l,p+mid,p+r+1);
it.p=p[mid];
it.msg.min[0]=it.msg.max[0]=it.p.x;
it.msg.min[1]=it.msg.max[1]=it.p.y;
Build(root<<1,l,mid-1,k^1),Build(root<<1|1,mid+1,r,k^1);
if(use[root<<1])
it.msg=lson.msg+it.msg;
if(use[root<<1|1])
it.msg=it.msg+rson.msg;
}
void read()
{
Read(n);
for(int i=1;i<=n;i++)
{
Read(p[i].x),Read(p[i].y);
p[i].id=i;
}
Build(1,1,n,0);
}
void Query(int root,const Point &a,int k)
{
Node temp=Node(Len(it.p,a),it.p.id);
int x=root<<1,y=root<<1|1;
flag=k;
if(Q.size()<m)
Q.push(temp);
else if(temp<Q.top())
Q.pop(),Q.push(temp);
if(a<it.p)
std::swap(x,y);
if(use[x]&&(Q.size()<m||tree[x].msg.dis(a)>=Q.top().dis))
Query(x,a,k^1);
if(use[y]&&(Q.size()<m||tree[y].msg.dis(a)>=Q.top().dis))
Query(y,a,k^1);
}
void ask()
{
int q;
Read(q);
Point a;
for(int i=1;i<=q;i++)
{
Read(a.x),Read(a.y),Read(m);
while(!Q.empty())
Q.pop();
Query(1,a,0);
printf("%d\n",Q.top().id);
}
}
int main()
{
read();
ask();
return 0;
}

  评论这张
 
阅读(573)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017