进口丰田越野车大全,无痛人流的价格,半导体空调
这个"\(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;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论