jason_yu表示是kd-tree的裸题。
拿个堆维护一下答案，然后剪剪枝啥的，写起来轻松愉快还比lct短。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long qw;
typedef pair <qw, int> hele;
#define _l (qw)
int _d_;
bool _nag_;
#define readInt(_x_) { \
int &_s_ = _x_; \
_s_ = 0; \
_nag_ = 0; \
while (!isdigit(_d_ = getchar())) \
if (_d_ == '-') \
_nag_ = 1; \
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
if (_nag_) \
_s_ = - _s_;\
}
const int maxn = 100009;
const int maxk = 23;
const qw qinf = 0x3f3f3f3f3f3f3f3fLL;
struct heap {
hele a[maxk];
int n;
inline heap() {
n = 0;
}
inline void clear() {
n = 0;
}
inline void push(hele x) {
a[n] = x;
push_heap(a, a + (++ n));
}
inline hele top() {
return a[0];
}
inline void pop() {
if (n)
pop_heap(a, a + (n --));
}
inline int size() {
return n;
}
};
struct kdnode {
int x, y, n;
int l, r, u, d;
kdnode *ls, *rs;
};
struct point {
int x, y, i;
};
inline bool cmpx(const point& a, const point& b) {
return a. x < b. x;
}
inline bool cmpy(const point& a, const point& b) {
return a. y < b. y;
}
inline qw sqr(const qw& a) {
return a * a;
}
int n, m, k;
heap ans;
kdnode *np, nlst[maxn];
point a[maxn];
#define upmax(_a_,_b_) { \
if (_a_ < _b_) \
_a_ = _b_; \
}
#define upmin(_a_,_b_) { \
if (_a_ > _b_) \
_a_ = _b_; \
}
inline void update(kdnode* p) {
p-> l = p-> x;
p-> r = p-> x;
p-> d = p-> y;
p-> u = p-> y;
if (p-> ls) {
upmin(p-> l, p-> ls-> l);
upmax(p-> r, p-> ls-> r);
upmin(p-> d, p-> ls-> d);
upmax(p-> u, p-> ls-> u);
}
if (p-> rs) {
upmin(p-> l, p-> rs-> l);
upmax(p-> r, p-> rs-> r);
upmin(p-> d, p-> rs-> d);
upmax(p-> u, p-> rs-> u);
}
}
kdnode* kdBuild(int l, int r, int d = 1) {
if (l >= r)
return 0;
kdnode* p = np ++;
int mid = (l + r) >> 1;
if (d)
nth_element(a + l, a + mid, a + r, cmpx);
else
nth_element(a + l, a + mid, a + r, cmpy);
p-> ls = kdBuild(l, mid, d ^ 1);
p-> rs = kdBuild(mid + 1, r, d ^ 1);
p-> x = a[mid]. x;
p-> y = a[mid]. y;
p-> n = a[mid]. i;
update(p);
return p;
}
inline hele guessDist(kdnode* p, int x, int y) {
return hele(-max(sqr(x - p-> l), sqr(x - p-> r))
- max(sqr(y - p-> u), sqr(y - p-> d)), -maxn);
}
void kdQry(kdnode* p, int x, int y) {
hele d(- sqr(p-> x - x) - sqr(p-> y - y), p-> n), dl, dr;
if (ans. size() < k || d < ans. top()) {
ans. push(d);
if (ans. size() > k)
ans. pop();
}
if (p-> ls)
dl = guessDist(p-> ls, x, y);
else
dl = hele(qinf, -maxn);
if (p-> rs)
dr = guessDist(p-> rs, x, y);
else
dr = hele(qinf, -maxn);
if (dl < dr) {
if (p-> ls && (dl < ans. top() || ans. size() < k))
kdQry(p-> ls, x, y);
if (p-> rs && (dr < ans. top() || ans. size() < k))
kdQry(p-> rs, x, y);
}
else {
if (p-> rs && (dr < ans. top() || ans. size() < k))
kdQry(p-> rs, x, y);
if (p-> ls && (dl < ans. top() || ans. size() < k))
kdQry(p-> ls, x, y);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
for (int i = 0; i < n; ++ i) {
readInt(a[i]. x);
readInt(a[i]. y);
a[i]. i = i + 1;
}
readInt(m);
np = nlst;
kdnode* rt = kdBuild(0, n);
while (m --) {
int x, y;
readInt(x);
readInt(y);
readInt(k);
ans. clear();
kdQry(rt, x, y);
printf("%d\n", ans. top(). second);
}
}