思路

这个"\(K\)远“点对一直理解成了距离第\(K\)大的点对\(233\)。

要求第\(K\)远，那么我们只要想办法求出来最远的\(K\)个点对就可以了。

用一个大小为\(2K\)(因为每个点对会被统计两次)的小头堆维护距离最大的\(K\)个点对，然后在\(KD-tree\)上查询最远点对，如果查到的点对之间的距离比堆顶大，那么就把堆顶弹出来，当前距离插进去。

最后堆顶元素就是答案。

代码

/*

* @Author: wxyww

* @Date:   2019-06-13 07:45:59

* @Last Modified time: 2019-06-13 08:47:21

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<ctime>

using namespace std;

typedef long long ll;

#define int ll

const int N = 100100,INF = 1e9;

#define ls TR[rt].ch[0]

#define rs TR[rt].ch[1]

priority_queue<int,vector<int>,greater<int> >q;

ll read() {

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') f=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9') {

		x=x*10+c-'0';

		c=getchar();

	}

	return x*f;

}

int mul(int x) {

	return x * x;

}

struct node {

	int ch[2],d[2],mx[2],mn[2];

}TMP,TR[N],a[N];

int D;

bool cmp(const node &A,const node &B) {

	return A.d[D] < B.d[D];

}

void up(int rt) {

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

		if(ls) TR[rt].mx[i] = max(TR[ls].mx[i],TR[rt].mx[i]),

			TR[rt].mn[i] = min(TR[ls].mn[i],TR[rt].mn[i]);

		if(rs) TR[rt].mx[i] = max(TR[rs].mx[i],TR[rt].mx[i]),

			TR[rt].mn[i] = min(TR[rs].mn[i],TR[rt].mn[i]);

	}

}

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

	D = now;

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

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

	TR[mid] = a[mid];

	for(int i = 0;i <= 1;++i) TR[mid].mx[i] = TR[mid].mn[i] = TR[mid].d[i];

	int rt = mid;

	if(l < mid) ls = build(l,mid - 1,now ^ 1);

	if(r > mid) rs = build(mid + 1,r,now ^ 1);

	up(mid);

	return mid;

}

int dis(const node &A,const node &B) {

	return mul(A.d[0] - B.d[0]) + mul(A.d[1] - B.d[1]);

}

int get(const node &A,const node &B) {

	int ret = 0;

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

		ret += mul(max(abs(A.d[i] - B.mx[i]),abs(A.d[i] - B.mn[i])));

	return ret;

}

void query(int rt) {

	int K = dis(TMP,TR[rt]);

	if(K > q.top()) q.pop(),q.push(K);

	int dl = -INF,dr = -INF;

	if(ls) dl = get(TMP,TR[ls]);

	if(rs) dr = get(TMP,TR[rs]);

	if(dl > dr) {

		if(dl > q.top()) query(ls);

		if(dr > q.top()) query(rs);

	}

	if(dr > dl) {

		if(dr > q.top()) query(rs);

		if(dl > q.top()) query(ls);

	}

}

int X[N],Y[N];

signed main() {

	int n = read(),K = read();

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

		X[i] = a[i].d[0] = read();Y[i] = a[i].d[1] = read();

	}

	int root = build(1,n,0);

	for(int i = 1;i <= K * 2;++i) q.push(0);

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

		TMP.d[0] = X[i],TMP.d[1] = Y[i];

		query(root);

	}

	cout<<q.top();

	return 0;

}

巴特西

bzoj4520 K远点对

思路

代码

最新文章

热门文章