bzoj 2626: JZPFAR k-D树

题目大意:

平面上n个点,每次给出一个点,求这个点的k远点

题解:

什么叫做k远点呢。。。

1 2 3 4 5中5是第一远,4是第二远...

看来我语文学的不好

那么我们直接上k-D Tree求k邻近的方式求k远离即可

#include <queue>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(ll &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

inline ll max(ll a,ll b,ll c){return max(a,max(b,c));}

inline ll min(ll a,ll b,ll c){return min(a,min(b,c));}

const ll maxn = 100010;

const ll dem = 2;

struct Node{

	Node *ch[2];

	ll pos[2];ll id;

	ll minn[2],maxx[2];

	void update(){

		for(ll d=0;d<dem;++d){

			minn[d] = min(pos[d],ch[0]->minn[d],ch[1]->minn[d]);

			maxx[d] = max(pos[d],ch[0]->maxx[d],ch[1]->maxx[d]);

		}

	}

}*null;

Node akdjalskjalksdlkasdlkjlkjflsgdjasdf;

Node T[maxn];

inline void init(){

	null = &akdjalskjalksdlkasdlkjlkjflsgdjasdf;

	null->ch[0] = null->ch[1] = null;

	for(ll d=0;d<dem;++d){

		null->pos[d] = 0;

		null->minn[d] = 0x3f3f3f3f;

		null->maxx[d] = -0x3f3f3f3f;

	}

}

ll now,split[maxn];

inline bool cmp(const Node &a,const Node &b){

	return a.pos[split[now]] < b.pos[split[now]];

}

Node* build(ll l,ll r,ll s){

	if(l > r) return null;

	ll mid = (l+r) >> 1;

	split[now = mid] = s % dem;

	nth_element(T+l,T+mid,T+r+1,cmp);

	Node *p = &T[mid];

	p->ch[0] = build(l,mid-1,s+1);

	p->ch[1] = build(mid+1,r,s+1);

	p->update();return p;

}

struct Data{

	ll dis;ll id;

	bool operator < (const Data &a)const{

		if(dis != a.dis) return dis > a.dis;

		return id < a.id;

	}

	Data(){}

	Data(ll a,ll b){dis=a;id=b;}

};

priority_queue<Data>q;

inline ll sqr(ll x){return x*x;}

Node op;ll k;

inline ll md(Node *p){

	ll ret = .0;

	ret = max(ret,sqr(p->minn[0] - op.pos[0]) + sqr(p->minn[1] - op.pos[1]));

	ret = max(ret,sqr(p->minn[0] - op.pos[0]) + sqr(p->maxx[1] - op.pos[1]));

	ret = max(ret,sqr(p->maxx[0] - op.pos[0]) + sqr(p->minn[1] - op.pos[1]));

	ret = max(ret,sqr(p->maxx[0] - op.pos[0]) + sqr(p->maxx[1] - op.pos[1]));

	return ret;

}

void query(Node *p){

	if(p == null) return;

	ll dis = 0;

	for(ll d=0;d<dem;++d) dis += sqr(op.pos[d] - p->pos[d]);

	if(q.size() < k){

		q.push(Data(dis,p->id));

	}else if(Data(dis,p->id) < q.top()){

		q.pop();q.push(Data(dis,p->id));

	}

	if(md(p->ch[0]) < md(p->ch[1])) swap(p->ch[0],p->ch[1]);

	if(p->ch[0] != null && ((q.size() < k) || (md(p->ch[0]) >= q.top().dis))) query(p->ch[0]);

	if(p->ch[1] != null && ((q.size() < k) || (md(p->ch[1]) >= q.top().dis))) query(p->ch[1]);

}

int main(){

	init();

	ll n;read(n);

	for(ll i=1;i<=n;++i){

		for(ll d=0;d<dem;++d){

			read(T[i].pos[d]);

		}

		T[i].ch[0] = T[i].ch[1] = null;

		T[i].id = i;T[i].update();

	}

	Node *root = build(1,n,1);

	ll m;read(m);

	while(m--){

		for(ll d=0;d<dem;++d) read(op.pos[d]);

		read(k);

		while(!q.empty()) q.pop();

		query(root);

		printf("%lld\n",q.top().id);

	}

	getchar();getchar();

	return 0;

}

巴特西

bzoj 2626: JZPFAR k-D树

题目大意:

题解:

最新文章

热门文章