题目描述

一个点每过一个单位时间就会向四个方向扩散一个距离,如图。

洛谷P1661 扩散-LMLPHP

两个点a、b连通,记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点,问最早什么时刻它们形成一个连通块。

输入输出格式

输入格式:

第一行一个数n,以下n行,每行一个点坐标。

【数据规模】

对于20%的数据,满足1≤N≤5; 1≤X[i],Y[i]≤50;

对于100%的数据,满足1≤N≤50; 1≤X[i],Y[i]≤10^9。

输出格式:

一个数,表示最早的时刻所有点形成连通块。

输入输出样例

输入样例#1:

2
0 0
5 5
输出样例#1:

5

两点间连边,距离为曼哈顿距离

答案等于(int)(最小生成树上最长边+1)/2

敲kruskal的时候居然漏掉了x=find(x)

因为写太快漏掉了吗?恐怕是因为那个瞬间没有走心

那样的瞬间还会出现多少次呢?

誰も知らない

 /*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct edge{
int x,y;
int d;
}e[mxn*mxn];
int mct=;
int cmp(edge a,edge b){
return a.d<b.d;
}
struct point{
int x,y;
}a[mxn];
int fa[mxn];
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int dist(int x,int y){
return abs(a[x].x-a[y].x)+abs(a[x].y-a[y].y);
}
//int mp[mxn][mxn];
int n,ans=;
void solve(){
int i,j;
for(i=;i<=n;i++)fa[i]=i;
int num=;
for(i=;i<=mct;i++){
int x=e[i].x;
int y=e[i].y;
x=find(x);y=find(y);
if(x!=y){
ans=max(ans,e[i].d);
num++;
fa[x]=y;
}
if(num==n)break;
}
return;
}
int main(){
int i,j;
n=read();
for(i=;i<=n;i++){
a[i].x=read();
a[i].y=read();
}
for(i=;i<n;i++)
for(j=i+;j<=n;j++){
e[++mct].x=i;e[mct].y=j;
e[mct].d=dist(i,j);
}
sort(e+,e+mct+,cmp);
//
solve();
printf("%d\n",(ans+)/);
return ;
}
05-04 12:10