1. 题目

传送门=￣ω￣=

题意：
首先给出 $n$个点，然后询问 $m$个坐标，对于每个坐标要求输出前面给出的 $n$个点中距离该坐标最近的 $k$个点是那些。

数据范围为 $50000$

2. 题解

具体做法参考这个题解：传送门=￣ω￣=

只不过是把曼哈顿距离改成了欧几里得距离，做法依然相同，甚至没有了插入操作。

至于要求输出前 $k$个最近点，搞个优先队列，队首元素距离最远，就方便剪枝，也方便删除无用答案。

代码：

#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>

#define NS (50005)
#define MKP make_pair

using namespace std;

typedef pair<int,int> PII;

template <typename _Tp>inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int squ(int a){return a * a;}

int n, ds, D, root, sz, m, k;

priority_queue<PII> pq;

stack<PII> ans;

struct N
{
    int d[5], mx[5], mn[5], l, r;
    int& operator [] (int a){return d[a];}
    bool operator < (N another) const {return d[D] < another[D];}
    void print()
    {
        for (int i = 0; i < ds - 1; i += 1) printf("%d ", d[i]);
        printf("%d\n", d[ds-1]);
    }
}arr[NS], e[NS], q;

void pup(int a)
{
    N& l = e[e[a].l], & r = e[e[a].r];
    for (int i = 0; i < ds; i += 1)
    {
        e[a].mx[i] = e[a].mn[i] = e[a][i];
        if (e[a].l)
        {
            e[a].mx[i] = max(e[a].mx[i], l.mx[i]);
            e[a].mn[i] = min(e[a].mn[i], l.mn[i]);
        }
        if (e[a].r)
        {
            e[a].mx[i] = max(e[a].mx[i], r.mx[i]);
            e[a].mn[i] = min(e[a].mn[i], r.mn[i]);
        }
    }
}

int dis(N p, int a)
{
    int tot = 0;
    for (int i = 0; i < ds; i += 1) tot += squ(p[i] - e[a][i]);
    return tot;
}

int get_dis(N p, int a)
{
    int tot = 0;
    for (int i = 0; i < ds; i += 1)
        tot += squ(max(e[a].mn[i] - p[i], 0)) + squ(max(p[i] - e[a].mx[i], 0));
    return tot;
}

void query(int a = root)
{
    if (!a) return;
    PII nxt = MKP(dis(q, a), a);
    if (pq.size() < k) pq.push(nxt);
    else if (nxt < pq.top()) pq.pop(), pq.push(nxt);
    int dl = INT_MAX, dr = INT_MAX;
    if (e[a].l) dl = get_dis(q, e[a].l);
    if (e[a].r) dr = get_dis(q, e[a].r);
    if (dl < dr)
    {
        if (dl < pq.top().first || pq.size() < k) query(e[a].l);
        if (dr < pq.top().first || pq.size() < k) query(e[a].r);
    }
    else
    {
        if (dr < pq.top().first || pq.size() < k) query(e[a].r);
        if (dl < pq.top().first || pq.size() < k) query(e[a].l);
    }
}

int Build(int l, int r, int d = 0)
{
    if (l > r) return 0;
    D = d;
    int a = ++sz, mid = (l + r) >> 1;
    nth_element(arr + l, arr + mid, arr + r + 1);
    e[a] = arr[mid];
    e[a].l = Build(l, mid - 1, (d + 1) % ds);
    e[a].r = Build(mid + 1, r, (d + 1) % ds);
    pup(a); return a;
}

int main (int argc, char const* argv[])
{
    while (sz = 0, ~scanf("%d%d", & n, & ds))
    {
        for (int i = 1; i <= n; i += 1)
            for (int j = 0; j < ds; j += 1)
                IN(arr[i][j]);
        root = Build(1, n), IN(m);
        while (m--)
        {
            for (int i = 0; i < ds; i += 1) IN(q[i]);
            IN(k), query();
            printf("the closest %d points are:\n", k);
            while (!pq.empty()) ans.push(pq.top()), pq.pop();
            while (!ans.empty()) e[ans.top().second].print(), ans.pop();
        }
    }
    return 0;
}