bzoj3053 The Closest M Points

题目链接

题意

思路

调到哭系列

其实就是kd-tree的模板题。用堆维护出距离最小的m个点。然后在\(kd-tree\)上查询。

这一个小地方从上午9点调到下午4点半。。。。。真的快气哭了。。。

代码

//调的心累呀！！！！
/*
* @author: wxyww
* @date:   2019-06-13 09:57:42
* @last modified time: 2019-06-13 16:35:15
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 500010,inf = 1e9;
#define ls tr[rt].ch[0]
#define rs tr[rt].ch[1]
#define pi pair<int,int>
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int d,wdk,tmp[n];
priority_queue<pi>q;
struct node {
    int ch[2],mx[6],mn[6],d[6];
}tr[n],a[n],tmp;
int mul(int x) {
    return x * x;
}
void up(int rt) {
    for(int i = 0;i < wdk;++i) {
        tr[rt].mx[i] = tr[rt].mn[i] = tr[rt].d[i];
        if(ls) tr[rt].mx[i] = max(tr[rt].mx[i],tr[ls].mx[i]),
            tr[rt].mn[i] = min(tr[rt].mn[i],tr[ls].mn[i]);
        if(rs) tr[rt].mx[i] = max(tr[rt].mx[i],tr[rs].mx[i]),
            tr[rt].mn[i] = min(tr[rt].mn[i],tr[rs].mn[i]);
    }
}
bool cmp(const node &a,const node &b) {
    return a.d[d] < b.d[d];
}
int build(int l,int r,int now) {
    if(l > r) return 0;
    d = now;
    int mid = (l + r) >> 1;
    nth_element(a + l ,a + mid,a + r + 1,cmp);
    int rt = mid;
    tr[mid] = a[mid];
     ls = build(l,mid - 1,(now + 1) % wdk);
     rs = build(mid + 1,r,(now + 1) % wdk);
    up(rt);
    return rt;
}
int dis(const node &a,const node &b) {
    int ret = 0;
    for(int i = 0;i < wdk;++i) ret += mul(a.d[i] - b.d[i]);
    return ret;
}
int get(const node &a,const node &b) {
    int ret = 0;
    for(int i = 0;i < wdk;++i)
        ret += mul(max(0,a.d[i] - b.mx[i])) + mul(max(0,b.mn[i] - a.d[i]));
    return ret;
}
void query(int rt) {
    if(!rt) return;
    int k = dis(tr[rt],tmp);
    if(k < q.top().first) q.pop(),q.push(make_pair(k,rt));
    int dl = inf,dr = inf;
    if(ls) dl = get(tmp,tr[ls]);
    if(rs) dr = get(tmp,tr[rs]);
    if(dl < dr) {
        if(dl < q.top().first) query(ls);
        if(dr < q.top().first) query(rs);
    }
    else {
        if(dr < q.top().first) query(rs);
        if(dl < q.top().first) query(ls);
    }
}

int main() {
    // freopen("3053/1.in","r",stdin);
    // freopen("m.out","w",stdout);
    int n;
    while(~scanf("%d%d",&n,&wdk)) {
        // cout<<n<<" "<<wdk<<endl;
        for(int i = 0;i < wdk;++i) a[0].mx[i] = -inf,a[0].mn[i] = inf;
        for(int i = 1;i <= n;++i) { 
            for(int j = 0;j < wdk;++j) {
                a[i].d[j] = read();
            }
        }
        int root = build(1,n,0);
        int t = read();
        // puts("!!!");
        while(t--) {

            for(int i = 0;i < wdk;++i) tmp.d[i] = read();
            int m = read();
            while(!q.empty()) q.pop();
            for(int i = 1;i <= m;++i) q.push(make_pair(inf,0));
            query(root);
            for(int i = 1;i <= m;++i) tmp[i] = q.top().second,q.pop();
            printf("the closest %d points are:\n",m);
            for(int i = m;i >= 1;--i) {
                for(int j = 0;j < wdk - 1;++j)
                    printf("%d ",a[tmp[i]].d[j]);
                printf("%d\n",a[tmp[i]].d[wdk - 1]);
            }

        }
    }
    return 0;
}
/*
6 2
2 9
6 9
4 4
7 5
8 1
9 6
1
5 1
*/