并查集加二分

#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/

floyd算法

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[55],b[55];
	cin>>n;
	for(int c=0;c<n;c++) cin>>a[c]>>b[c];
	int i[55][55];
	for(int c=0;c<n;c++){
		for(int d=0;d<c;d++){
			i[c][d]=i[d][c]=abs(a[c]-a[d])+abs(b[c]-b[d]);
		}
	}
	for(int k=0;k<n;k++){
		for(int c=0;c<n;c++){
			for(int d=0;d<n;d++){
				i[c][d]=min(i[c][d],max(i[c][k],i[k][d]));
			}
		}
	}
	int ans=0;
	for(int c=0;c<n;c++){
		for(int d=0;d<c;d++){
			ans=max(ans,i[c][d]);
		}
	}
	cout<<(ans+1)/2;
}

这道题似乎可以用并查集干 但是我干不来