居然是KD解。
/* 4347 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 int id, n, m, K; typedef struct node_t {
int x[]; friend bool operator< (const node_t& a, const node_t& b) {
return a.x[id] < b.x[id];
} double Distance(const node_t& a) {
__int64 ret = ; rep(i, , K)
ret += 1LL*(a.x[i]-x[i])*(a.x[i]-x[i]); return ret;
} void print() {
printf("%d", x[]);
rep(i, , K)
printf(" %d", x[i]);
putchar('\n');
} } node_t; typedef struct Node {
__int64 d;
node_t p; Node() {}
Node(__int64 d, node_t& p):
d(d), p(p) {} friend bool operator< (const Node& a, const Node& b) {
return a.d < b.d;
} } Node; const int maxn = ;
node_t nd[maxn];
vector<node_t> ans; typedef struct KD_tree{
static const int maxd = ;
static const int maxn = ;
node_t P[maxn<<];
int idx[maxn<<];
priority_queue<Node> Q; void Build(int deep, int l, int r, int rt) {
if (l > r)
return ;
idx[rt] = deep % K;
if (l == r) {
P[rt] = nd[l];
return ;
} id = idx[rt];
int mid = (l + r) >> ;
nth_element(nd+l, nd+mid, nd+r+);
P[rt] = nd[mid];
Build(deep+, l, mid-, rt<<);
Build(deep+, mid+, r, rt<<|);
} void Query(node_t x, int l, int r, int rt) {
if (l > r)
return ; int id = idx[rt];
__int64 tmp = x.Distance(P[rt]);
if (l == r) {
if (SZ(Q) < m) {
Q.push(Node(tmp, P[rt]));
} else {
if (tmp < Q.top().d) {
Q.pop();
Q.push(Node(tmp, P[rt]));
}
}
return ;
} int mid = (l + r) >> ; if (P[rt].x[id] >= x.x[id]) {
Query(x, l, mid-, rt<<);
if (SZ(Q) < m) {
Q.push(Node(tmp, P[rt]));
Query(x, mid+, r, rt<<|);
} else {
if (tmp < Q.top().d) {
Q.pop();
Q.push(Node(tmp, P[rt]));
}
if (1LL*(x.x[id]-P[rt].x[id])*(x.x[id]-P[rt].x[id]) < Q.top().d) {
Query(x, mid+, r, rt<<|);
}
}
} else {
Query(x, mid+, r, rt<<|);
if (SZ(Q) < m) {
Q.push(Node(tmp, P[rt]));
Query(x, l, mid-, rt<<);
} else {
if (tmp < Q.top().d) {
Q.pop();
Q.push(Node(tmp, P[rt]));
}
if (1LL*(x.x[id]-P[rt].x[id])*(x.x[id]-P[rt].x[id]) < Q.top().d) {
Query(x, l, mid-, rt<<);
}
}
}
} void Dump() {
ans.clr();
while (!Q.empty()) {
ans.pb(Q.top().p);
Q.pop();
}
}
} KD_tree; KD_tree kd; void solve() {
int q, sz;
node_t p; kd.Build(, , n-, );
scanf("%d", &q);
while (q--) {
rep(j, , K)
scanf("%d", &p.x[j]);
scanf("%d", &m);
kd.Query(p, , n-, );
kd.Dump();
sz = SZ(ans);
printf("the closest %d points are:\n", m);
per(i, , sz) {
ans[i].print();
}
}
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif while (scanf("%d %d", &n, &K)!=EOF) {
rep(i, , n)
rep(j, , K)
scanf("%d", &nd[i].x[j]);
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
数据发生器。
from copy import deepcopy
from random import randint, shuffle
import shutil
import string def GenDataIn():
with open("data.in", "w") as fout:
t = 10
bound = 10**5
for tt in xrange(t):
n = randint(100, 200)
k = randint(1, 5)
fout.write("%d %d\n" % (n, k))
for i in xrange(n):
L = []
for j in xrange(k):
x = randint(-1000, 1000)
L.append(x)
fout.write(" ".join(map(str, L)) + "\n")
q = randint(20, 30)
fout.write("%d\n" % (q))
for qq in xrange(q):
L = []
for j in xrange(k):
x = randint(-1000, 1000)
L.append(x)
fout.write(" ".join(map(str, L)) + "\n")
m = randint(1, 10)
fout.write("%d\n" % (m)) def MovDataIn():
desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
shutil.copyfile("data.in", desFileName) if __name__ == "__main__":
GenDataIn()
MovDataIn()