【題目描述】

一個點每過一個單位時間就會向四個方向擴散一個距離，如圖。

兩個點a、b連通，記作e(a,b),當且僅當a、b的擴散區域有公共部分。連通塊的定義是塊內的任意兩個點u、v都必定存在路徑e(u,a0),e(a0,a1),…,e(ak,v)。給定平面上的n給點，問最早什么時刻它們形成一個連通塊。

【輸入】

第一行一個數n，以下n行，每行一個點坐標。

【輸出】

一個數，表示最早的時刻所有點形成連通塊。

【輸入樣例】

2
0 0
5 5

【輸出樣例】

5

【源程序】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const double EPS = 1E-10; const int MOD = 1E9+7; const int N = 1000000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; struct Edge{int x,y;int dis;Edge(){}Edge(int x,int y,int dis):x(x),y(y),dis(dis){}bool operator < (const Edge &rhs)const{return dis<rhs.dis;} }edge[N]; struct Node{int x,y;Node(){}Node(int x,int y):x(x),y(y){} }node[N]; int tot; int father[N]; int getDis(int i,int j){return abs(node[i].x-node[j].x)+abs(node[i].y-node[j].y); } int Find(int x){return father[x]==x?x:father[x]=Find(father[x]); } int Kruskal(int n){for(int i=1;i<=n;i++)father[i]=i;int num=0;int res=-INF;for(int i=1;i<=tot;i++){int x=edge[i].x;int y=edge[i].y;x=Find(x);y=Find(y);if(x!=y){res=max(res,edge[i].dis);num++;father[x]=y;}if(num==n)break;}return res; } int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&node[i].x,&node[i].y);for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){edge[++tot].x=i;edge[tot].y=j;edge[tot].dis=getDis(i,j);}}sort(edge+1,edge+1+tot);int res=Kruskal(n);res=(res+1)/2;printf("%d\n",res);return 0; }

?

總結

以上是生活随笔為你收集整理的扩散（信息学奥赛一本通-T1437）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。