loj2043 「CQOI2016」K 远点对

k-d tree 裸题………………
#include <algorithm>

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, k, rot, nowD, din;

ll dui[205];

const ll oo=9e18;

struct Point{

	int d[2], mn[2], mx[2], l, r;

	int & operator[](int x){

		return d[x];

	}

	bool operator<(const Point &x)const{

		return d[nowD]<x.d[nowD];

	}

}p[100005], T;

bool cmp(ll x, ll y){

	return x>y;

}

struct KDTree{

	Point t[100005];

	void pushUp(int k){

		int l=t[k].l, r=t[k].r;

		for(int i=0; i<2; i++){

			t[k].mn[i] = t[k].mx[i] = t[k][i];

			if(l){

				t[k].mn[i] = min(t[k].mn[i], t[l].mn[i]);

				t[k].mx[i] = max(t[k].mx[i], t[l].mx[i]);

			}

			if(r){

				t[k].mn[i] = min(t[k].mn[i], t[r].mn[i]);

				t[k].mx[i] = max(t[k].mx[i], t[r].mx[i]);

			}

		}

	}

	int build(int l, int r, int now){

		nowD = now;

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

		nth_element(p+l, p+mid, p+r+1);

		t[mid] = p[mid];

		if(l<mid)	t[mid].l = build(l, mid-1, now^1);

		if(mid<r)	t[mid].r = build(mid+1, r, now^1);

		pushUp(mid);

		return mid;

	}

	ll getDis(const Point &u, const Point &v){

		return (ll)(u.d[1]-v.d[1])*(u.d[1]-v.d[1])+(ll)(u.d[0]-v.d[0])*(u.d[0]-v.d[0]);

	}

	ll simDis(int k){

		ll re=0;

		for(int i=0; i<2; i++){

			ll tmp=max(abs(t[k].mn[i]-T[i]), abs(t[k].mx[i]-T[i]));

			re += tmp * tmp;

		}

		return re;

	}

	void query(int k){

		ll d=getDis(t[k], T), disl=-oo, disr=-oo;

		int l=t[k].l, r=t[k].r;

		if(d>dui[1]){

			pop_heap(dui+1, dui+1+din, cmp);

			dui[din] = d;

			push_heap(dui+1, dui+1+din, cmp);

		}

		if(l)	disl = simDis(l);

		if(r)	disr = simDis(r);

		if(disl>disr){

			if(disl>dui[1])	query(l);

			if(disr>dui[1])	query(r);

		}

		else{

			if(disr>dui[1])	query(r);

			if(disl>dui[1])	query(l);

		}

	}

}kdt;

int main(){

	cin>>n>>k;

	k *= 2;

	for(int i=1; i<=n; i++)

		scanf("%d %d", &p[i][0], &p[i][1]);

	rot = kdt.build(1, n, 0);

	while(k--)	dui[++din] = -oo;

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

		T = p[i];

		kdt.query(rot);

	}

	cout<<dui[1]<<endl;

	return 0;

}
巴特西

loj2043 「CQOI2016」K 远点对

最新文章

热门文章
