bzoj 3053 The Closest M Points
- 钱限题.题面可以看这里.
- 用 \(kd-tree\) 来做.
- \(k\) 维空间找一次最近点,时间复杂度大致为 \(O(kn^{1-\frac 1 k})\) .讲题人表示这个的时间复杂度可能是 \(fAKe\) 的...但一般情况下都不会去卡 \(kd-tree\) ,而且前提是 \(std\) 不是 \(kd-tree\) .
如果硬要卡,曼哈顿距离的题可以把绝大部分点放在直线 \(y=x+C\) 上,欧几里得距离的题可以把绝大部分点放在同一个圆上.这样使得估价函数无法有效剪枝, \(kd-tree\) 会将所有子树遍历一遍.
- 具体做法是配合堆使用,开一个大根堆,每次询问时放 \(m\) 个 \(inf\) 进去,然后查询的时候,找到的点若比堆顶优,就弹出堆顶,加入新点.其他部分的操作,就和询问最近的 \(1\) 个点类似了.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int sqr(int x)
{
return x*x;
}
inline int read()
{
int x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
const int MAXN=5e4+10;
int n,m,k,rt=0,Tp;
struct point{
int d[5];
int& operator[] (int x)
{
return d[x];
}
bool operator < (const point &rhs) const
{
return d[Tp]<rhs.d[Tp];
}
friend int dist(point a,point b)
{
int res=0;
for(int i=0;i<k;++i)
res+=sqr(a[i]-b[i]);
return res;
}
};
point P[MAXN],qnode;
struct node{
point x;
int mi[5],ma[5];
int ls,rs;
}Tree[MAXN];
#define root Tree[o]
#define lson Tree[root.ls]
#define rson Tree[root.rs]
#define inf 0x7f7f7f7f
priority_queue<pii,vector <pii> ,less <pii> > q;
inline void pushup(int o)
{
for(int i=0;i<k;++i)
{
if(root.ls)
{
root.mi[i]=min(root.mi[i],lson.mi[i]);
root.ma[i]=max(root.ma[i],lson.ma[i]);
}
if(root.rs)
{
root.mi[i]=min(root.mi[i],rson.mi[i]);
root.ma[i]=max(root.ma[i],rson.ma[i]);
}
}
}
void BuildTree(int& o,int l,int r,int tp)
{
Tp=tp;
int mid=(l+r)>>1;
o=mid;
root.ls=root.rs=0;
nth_element(P+l,P+mid,P+r+1);
root.x=P[mid];
for(int i=0;i<k;++i)
root.ma[i]=root.mi[i]=root.x[i];
if(l<=mid-1)
BuildTree(root.ls,l,mid-1,(tp+1)%k);
if(mid+1<=r)
BuildTree(root.rs,mid+1,r,(tp+1)%k);
pushup(o);
}
int calc(int o)
{
if(!o)
return inf;
int res=0;
for(int i=0;i<k;++i)
{
if(qnode[i]<root.mi[i])
res+=sqr(qnode[i]-root.mi[i]);
if(qnode[i]>root.ma[i])
res+=sqr(qnode[i]-root.ma[i]);
}
return res;
}
void query(int o)
{
int tmp=dist(root.x,qnode);
if(tmp<q.top().first)
{
q.pop();
q.push(mp(tmp,o));
}
int dl=calc(root.ls),dr=calc(root.rs);
if(dl<dr)
{
if(dl<q.top().first)
query(root.ls);
if(dr<q.top().first)
query(root.rs);
}
else
{
if(dr<q.top().first)
query(root.rs);
if(dl<q.top().first)
query(root.ls);
}
}
int ans[11];
int main()
{
// freopen("1.in","r",stdin);
// freopen("ans.out","w",stdout);
while(~scanf("%d%d",&n,&k))
{
for(int i=1;i<=n;++i)
for(int j=0;j<k;++j)
P[i][j]=read();
BuildTree(rt,1,n,0);
int Q=read();
while(Q--)
{
for(int i=0;i<k;++i)
qnode[i]=read();
int m=read();
for(int i=1;i<=m;++i)
q.push(mp(inf,0));
query(rt);
printf("the closest %d points are:\n",m);
for(int i=0;i<m;++i)
{
ans[i]=q.top().second;
q.pop();
}
for(int i=m-1;i>=0;--i)
{
for(int j=0;j<k;++j)
printf("%d ",Tree[ans[i]].x[j]);
puts("");
}
}
}
return 0;
}