KD tree 超时求助
查看原帖
KD tree 超时求助
87651
www2003楼主2022/1/20 11:18
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

struct node{
	double x,y;
}a[202020];

inline bool cmp1(const node &aa,const node &bb)
{
	return aa.x < bb.x;
}

inline bool cmp2(const node &aa,const node &bb)
{
	return aa.y < bb.y;
}

#define poww(a) (a) * (a)
int n,now;
double ans;
int tree[1010101]; 

inline double dis(int u,int v)
{
	return poww(a[u].x - a[v].x) + poww(a[u].y - a[v].y);
}

int assess(int l,int r)
{
	double tot1 = 0,tot2 = 0,ave1 = 0,ave2 = 0;
	for(int i = l; i <= r; i++)ave1 += a[i].x,ave2 += a[i].y;
	ave1 /= (r - l + 1),ave2 /= (r - l + 1);
	for(int i = l; i <= r; i++)tot1 += poww(a[i].x - ave1),tot2 += poww(a[i].y - ave2);
	return tot1 >= tot2;
}

void build(int k,int l,int r)
{
	if(l >= r)return;
	int m = l + r >> 1;
	tree[k] = assess(l,r);
	if(tree[k] == 1)nth_element(a + l,a + m,a + r,cmp1);
	else nth_element(a + l,a + m,a + r,cmp2);
	build(k << 1,l,m-1);
	build(k <<1|1,m+1,r);
}

void query(int k,int l,int r)
{
	if(r <= now)return;
	int m = l + r >> 1;
	if(now != m)ans = min(ans,dis(now,m));
	if(l >= r)return;
	if(tree[k] == 1)
	{
		if(a[now].x < a[m].x)
		{
			query(k << 1,l,m-1);
			if(ans > fabs(a[now].x - a[m].x))query(k << 1|1,m+1,r);	
		}
		else
		{
			query(k << 1|1,m+1,r);
			if(ans > fabs(a[now].x - a[m].x))query(k << 1,l,m-1);	
		} 
	}
	else
	{
		if(a[now].y < a[m].y)
		{
			query(k<<1,l,m-1);
			if(ans > fabs(a[now].y - a[m].y))query(k<<1|1,m+1,r);	
		}
		else
		{
			query(k<<1|1,m+1,r);
			if(ans > fabs(a[now].y - a[m].y))query(k << 1,l,m-1);	
		} 
	}
}

int main()
{
	ans = 1e22; 
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lf%lf",&a[i].x,&a[i].y);
	}
	build(1,1,n);
	for(now = 1; now <= n; now++)
	{
		query(1,1,n);
	}
	printf("%.4lf",sqrt(ans));
    return 0;
}
2022/1/20 11:18
加载中...