并查集加二分

#include<iostream>
#include<cmath>
using namespace std;

int n,d[57][57],f[57];
struct A{
	int  x,y;
}p[57];

int juli(A n1,A n2){
	return abs(n1.x-n2.x)+abs(n1.y-n2.y);
}

int find(int x){
	if(x==f[x])return x;
	else return f[x]=find(f[x]);
}

bool check(int  x){
	for(int i=0;i<n;i++)f[i]=i;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(d[i][j]<=x*2){
				int fx=find(i),fy=find(j);
				if(fx!=fy)f[fx]=fy;
			}
		}
	}
	int sum=0;
	for(int i=0;i<n;i++){
		if(f[i]==i)sum++;
		if(sum>=2)return false ;
	}
	return true;
}

int search(int l,int r){
	int mid;
	while(l<=r){
		mid=(l+r+1)>>1;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	return l;
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>p[i].x>>p[i].y;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			d[i][j]=juli(p[i],p[j]);
			d[j][i]=d[i][j];
		}
	}
	int ans=search(0,500000000);
	cout<<ans;
	return 0;
}

详情移步https://dueyin.github.io/posts/kmp_and_-sort/