60pts求助
查看原帖
60pts求助
334309
L_C_T楼主2021/12/9 19:39
#include<bits/stdc++.h>
using namespace std;
#define debug cerr<<114514
const int maxn=2e5+10;
int n,d[maxn],lson[maxn],rson[maxn];
double ans=2e18,ans1;
struct node{
	double x,y; 
}s[maxn];
double L[maxn],D[maxn],R[maxn],U[maxn];
double dis(int a,int b){
	return (s[a].x-s[b].x)*(s[a].x-s[b].x)+(s[a].y-s[b].y)*(s[a].y-s[b].y);
}
bool cmp1(node a,node b){return a.x<b.x;}
bool cmp2(node a,node b){return a.y<b.y;}

void pushdown(int x){
	L[x]=R[x]=s[x].x;
	D[x]=U[x]=s[x].y;
	if(lson[x]){
		L[x]=min(L[x],L[lson[x]]);R[x]=max(R[x],R[lson[x]]);
		D[x]=min(D[x],D[lson[x]]);U[x]=max(U[x],U[lson[x]]);
	}
	if(rson[x]){
		L[x]=min(L[x],L[rson[x]]);R[x]=max(R[x],R[rson[x]]);
		D[x]=min(D[x],D[rson[x]]);U[x]=max(U[x],U[rson[x]]);
	}
}
double f(int a,int b){
	double res=0;
	if(L[b]>s[a].x) res+=(L[b]-s[a].x)*(L[b]-s[a].x);
	if(R[b]<s[a].x) res+=(s[a].x-R[b])*(s[a].x-R[b]);
	if(D[b]>s[a].y) res+=(D[b]-s[a].y)*(D[b]-s[a].y);
	if(U[b]<s[a].y) res+=(s[a].y-U[b])*(s[a].y-U[b]);
	return res;
}
int build(int l,int r){
	if(l>=r) return 0;
	int mid=(l+r)/2;
	double avx=0,avy=0,vax=0,vay=0;
	for(int i=l;i<=r;i++) avx+=s[i].x,avy+=s[i].y;
	avx/=(double)(r-l+1);
	avy/=(double)(r-l+1);
	for(int i=l;i<=r;i++)
		vax+=(s[i].x-avx)*(s[i].x-avx),
		vay+=(s[i].y-avy)*(s[i].y-avy);
	if(vax>=vay) d[mid]=1,nth_element(s+l,s+mid,s+r+1,cmp1);
	else d[mid]=2,nth_element(s+l,s+mid,s+r+1,cmp2);
	lson[mid]=build(l,mid-1);
	rson[mid]=build(mid+1,r);
	pushdown(mid);
	return mid;
}
double f1(int a,int b){
	double res=0;
	if(L[b]<s[a].x) res+=(L[b]-s[a].x)*(L[b]-s[a].x);
	if(R[b]>s[a].x) res+=(s[a].x-R[b])*(s[a].x-R[b]);
	if(D[b]<s[a].y) res+=(D[b]-s[a].y)*(D[b]-s[a].y);
	if(U[b]>s[a].y) res+=(s[a].y-U[b])*(s[a].y-U[b]);
	return res;
}
void query1(int l,int r,int x){
	if(l>r) return;
	int mid=(l+r)/2;
	if(mid!=x) ans=min(ans,dis(x,mid));
	if(l==r) return;
	double disl=f(x,lson[mid]),disr=f(x,rson[mid]);
	if(disl<ans&&disr<ans){
		if(disl<disr){
			query1(l,mid-1,x);
			query1(mid+1,r,x);
		}
		else{
			query1(mid+1,r,x);
			query1(l,mid-1,x);
		}
	}
	else{
		if(disl<ans) query1(l,mid-1,x);
		if(disr<ans) query1(mid+1,r,x);
	}
}
void query2(int l,int r,int x){
	if(l>r) return;
	int mid=(l+r)/2;
	if(mid!=x) ans1=max(ans1,dis(x,mid));
	if(l==r) return;
	double disl=f1(x,lson[mid]),disr=f1(x,rson[mid]);
	if(disl>ans1&&disr>ans1){
		if(disl>disr){
			query2(l,mid-1,x);
			query2(mid+1,r,x);
		}
		else{
			query2(mid+1,r,x);
			query2(l,mid-1,x);
		}
	}
	else{
		if(disl>ans1) query2(l,mid-1,x);
		if(disr>ans1) query2(mid+1,r,x);
	}
}
int main(){
//	freopen("1.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&s[i].x,&s[i].y);
	build(1,n);
	for(int i=1;i<=n;i++) query1(1,n,i),query2(1,n,i);
	printf("%.2lf %.2lf\n",sqrt(ans),sqrt(ans1));
	return 0;
}
2021/12/9 19:39
加载中...