C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 496K, 提交时间: 2020-02-15 21:21:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dis[55][55];
struct node {
	int x,y;
}a[55];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			
				dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]));
	int ans=-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ans=max(1ll*ans,dis[i][j]);
	cout<<(ans+1)/2<<"\n"; 
	return 0;
} 

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 404K, 提交时间: 2020-02-20 16:58:23

#include<bits/stdc++.h>
using namespace std;
int x[55],y[55];
int w[55][55];//记录的是两个点之间的距离 
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			w[i][j]=w[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				w[i][j]=min(w[i][j],max(w[i][k],w[k][j]));
	int ans=0;//记录最小的时刻 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			ans=max(ans,w[i][j]);
	printf("%d\n",(ans+1)/2); 
	return 0;
}