AcWing 4179. 扩散
原题链接
简单
作者:
千木流烟
,
2024-04-11 19:44:43
,
所有人可见
,
阅读 13
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
int n;//点的个数
int a[60];//存每个点的X+Y
PII point[60];//存每个点的数组
int p[60];
int find(int x){//并查集
if (p[x]!=x) p[x]=find(p[x]);
return p[x];
}
bool check(int mid)//判断是不是连通块
{
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
if(abs(point[i].first-point[j].first)+abs(point[i].second-point[j].second)<=mid*2){
p[find(j)]=find(i);
}else{
continue;
}
}
int cnt=0;
for(int i=1;i<n;i++){
if(find(i)==find(0))
cnt++;
}
if(cnt==n-1) //回溯并查集状态
{
for(int i=0;i<n;i++) p[i]=i;
return true;
}
else{
for(int i=0;i<n;i++) p[i]=i;
return false;
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)//存点
{
int x,y;
scanf("%d%d",&x,&y);
point[i].first = x;
point[i].second = y;
p[i]=i;//初始化
a[i]=x+y;
}
sort(a,a+n);
//开始二分
int l=0,r=a[n-1]-a[0];
while(l<r){
int mid = (l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d",l);
return 0;
}