laekov

BZOJ2626 JZPFAR

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);

}

}


评论

© laekov | Powered by LOFTER