The Closest M Points
【问题描述】
软工学院的课程很讨厌！ZLC同志遇到了一个头疼的问题：在K维空间里面有许多的点，对于某些给定的点，ZLC需要找到和它最近的m个点。
（这里的距离指的是欧几里得距离：D(p, q) = D(q, p) = sqrt((q1 - p1) ^ 2 + (q2 - p2) ^ 2 + (q3 - p3) ^ 2 + ... + (qn - pn) ^ 2)
ZLC要去打Dota，所以就麻烦你帮忙解决一下了……
【输入格式】
第一行，两个非负整数：点数n(1 <= n <= 50000)，和维度数k(1 <= k <= 5)。
接下来的n行，每行k个整数，代表一个点的坐标。
接下来一个正整数：给定的询问数量t(1 <= t <= 10000)
下面2*t行：
第一行，k个整数：给定点的坐标
第二行：查询最近的m个点(1 <= m <= 10)
所有坐标的绝对值不超过10000。
有多组数据！
【输出格式】
对于每个询问，输出m+1行：
第一行："the closest m points are:" m为查询中的m
接下来m行每行代表一个点，按照从近到远排序。
保证方案唯一，下面这种情况不会出现：
2 2
1 1
3 3
1
2 2
1
【样例输入】
3 2
1 1
1 3
3 4
2
2 3
2
2 3
1
【样例输出】
5
0
4
题解：
题意就是求与给定点第一近到第m近的点
用KD树查询
期望答案的计算：与给定点最近且不与给定点在同一块的期望点必定在边界上
开始时先将m个inf加入
那么当查询到的点与给定点的距离小于堆顶与给定点的距离时，就去掉堆顶并加入这个点
最后倒序输出
注意初始化（虽然没写什么初始化，但是要考虑一下的）
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline void Scan(int &x)
{
int o = ;
char c;
while((c = getchar()) < '' || c > '')
if(c == '-') o = -;
x = c - '';
while((c = getchar()) >= '' && c <= '') x = x * + c - '';
x *= o;
}
const int me = ;
const int inf = ;
struct dot
{
int lc, rc;
int dis;
int v[], mi[], ma[];
};
dot point;
dot c[me];
dot tr[me];
dot ans[me];
struct name
{
int x;
int dis;
};
inline bool operator < (const name &a, const name &b)
{
return a.dis < b.dis;
}
priority_queue <name> sta;
int e, n, k, m;
inline bool cmp(const dot &a, const dot &b)
{
return a.v[e] < b.v[e];
}
inline int Min(const int &x, const int &y)
{
return (x < y) ? x : y;
}
inline int Max(const int &x, const int &y)
{
return (x > y) ? x : y;
}
inline int Sqr(const int &x)
{
return x * x;
}
inline void Update(const int &x)
{
int l = tr[x].lc, r = tr[x].rc;
for(int i = ; i < k; ++i)
{
tr[x].mi[i] = tr[x].ma[i] = tr[x].v[i];
if(l) tr[x].mi[i] = Min(tr[x].mi[i], tr[l].mi[i]), tr[x].ma[i] = Max(tr[x].ma[i], tr[l].ma[i]);
if(r) tr[x].mi[i] = Min(tr[x].mi[i], tr[r].mi[i]), tr[x].ma[i] = Max(tr[x].ma[i], tr[r].ma[i]);
}
}
int Build(const int &l, const int &r, int d)
{
if(d >= k) d -= k;
e = d;
int mi = l + r >> ;
nth_element(c + l, c + mi, c + r + , cmp);
tr[mi] = c[mi];
if(l < mi) tr[mi].lc = Build(l, mi - , d + );
if(r > mi) tr[mi].rc = Build(mi + , r, d + );
Update(mi);
return mi;
}
inline int Dis(const int &x)
{
int sum = ;
for(int i = ; i < k; ++i)
sum += Sqr(tr[x].v[i] - point.v[i]);
return sum;
}
inline int Get(const int &x)
{
int sum = ;
for(int i = ; i < k; ++i)
{
if(point.v[i] < tr[x].mi[i]) sum += Sqr(tr[x].mi[i] - point.v[i]);
if(point.v[i] > tr[x].ma[i]) sum += Sqr(point.v[i] - tr[x].ma[i]);
}
return sum;
}
void Ask(const int &x)
{
int dis = Dis(x);
if(dis < sta.top().dis)
{
sta.pop();
sta.push((name) {x, dis});
}
int le = inf, ri = inf;
if(tr[x].lc) le = Get(tr[x].lc);
if(tr[x].rc) ri = Get(tr[x].rc);
if(le < ri)
{
if(le < sta.top().dis) Ask(tr[x].lc);
if(ri < sta.top().dis) Ask(tr[x].rc);
}
else
{
if(ri < sta.top().dis) Ask(tr[x].rc);
if(le < sta.top().dis) Ask(tr[x].lc);
}
}
int main()
{
// freopen("d.in", "r", stdin), freopen("d.out", "w", stdout);
while(~scanf("%d", &n))
{
Scan(k);
for(int i = ; i <= n; ++i)
for(int j = ; j < k; ++j)
Scan(c[i].v[j]);
int root = Build(, n, );
int t;
Scan(t);
while(t--)
{
for(int i = ; i < k; ++i) Scan(point.v[i]);
Scan(m);
for(int i = ; i <= m; ++i) sta.push((name) {, inf});
Ask(root);
for(int i = ; i <= m; ++i)
{
ans[i] = tr[sta.top().x];
sta.pop();
}
printf("the closest %d points are:\n", m);
for(int i = m; i >= ; --i)
{
for(int j = ; j < k - ; ++j)
printf("%d ", ans[i].v[j]);
printf("%d\n", ans[i].v[k - ]);
}
}
}
}