WA 95 pts。无TLE、MLE、RE等。

求调！望大佬相助

做法:分治。

具体的，是对坐标x进行sort，再分治。

复杂度：O（n*log n）

My Record

#include<bits/stdc++.h> 
#define fileio(filename) freopen(filename".in","r",stdin),freopen(filename".out","w",stdout) 

#define int long long 

using namespace std; 
namespace FastIO {  
	inline int read() {
		int x=0,f=1;char c=getchar();
		while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); }
		while(c<='9'&&c>='0') { x=(x<<3)+(x<<1)+c-48; c=getchar(); }
		return x*f;
	}
	inline void __WriteNumbersIO(int x) {
		if(x>9) __WriteNumbersIO(x/10);
		putchar(x%10+48);
	}
	inline void pt(int x) {
		if(x==0) { putchar('0'); return; }
		if(x<0) putchar('-'),x=-x;
		__WriteNumbersIO(x);
	}
}
using namespace FastIO; 
const int inf = 1e18;
const int N = 400400; 
int n,m; 
struct point { 
	int x,y;
	void Rd() {
		x=read();
		y=read();
	}
	int dis(point bb) {
		return (x-bb.x)*(x-bb.x)+(y-bb.y)*(y-bb.y);
	}
}e[N],h[N],f[N];
 
bool Cmpx(point aa,point bb) { 
	if(aa.x^bb.x)return aa.x<bb.x;  
	return aa.y<bb.y;
} 
int cdq(int l,int r) { 
	if(l==r) return inf; 
	if(l+1==r) return e[l].dis(e[r]); 
	int mid=l+r>>1;
	int s=e[mid].x; 
	int d=min(cdq(l,mid),cdq(mid+1,r)); 
	int cnt=0,lp=l,rp=mid+1; 
	while(lp<=mid&&rp<=r) { 
		if(e[lp].y<e[rp].y) { 
			h[++cnt]=e[lp]; 
			lp++; 
		} else { 
			h[++cnt]=e[rp]; 
			rp++; 
		} 
	}
	while(lp<=mid) h[++cnt]=e[lp],lp++;
	while(rp<=r) h[++cnt]=e[rp],rp++;
	for(int i=1;i<=cnt;i++)
		e[i+l-1]=h[i];
	int len=0;
	for(int i=1;i<=cnt;i++) {
		if((h[i].x-s)*(h[i].x-s)<=d) f[++len]=h[i];
	}
	for(int i=1;i<=len;i++) { 
		for(int j=i-1;j>=1;j--) { 
			if( (f[i].y-f[j].y)*(f[i].y-f[j].y) >= d ) break; 
			d=min(d, f[i].dis(f[j]) ); 
		} 
		for(int j=i+1;j<=len;j++) { 
			if( (f[j].y-f[i].y)*(f[j].y-f[i].y) >= d ) break; 
			d=min(d, f[i].dis(f[j]) ); 
		} 
	} 
	return d; 
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) e[i].Rd();
	sort(e+1,e+1+n,Cmpx);
	pt(cdq(1,n));
	return 0;
}