记录编号 22249 评测结果 AAAAAAAAAA
题目名称 扩散 最终得分 100
用户昵称 Gravatar苏轼 是否通过 通过
代码语言 C++ 运行时间 0.020 s
提交时间 2010-11-18 11:57:22 内存使用 0.23 MiB
显示代码纯文本
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=50;
struct Node
{
	int dis;
	int u,v;
	Node(int a,int b,int c):dis(a),u(b),v(c){}
};

vector<Node> v;

bool operator < (const Node &a,const Node &b)
{
	return a.dis<b.dis;
}

int father[MAXN];
inline int getfather(int u)
{
	if (father[u]==u) return u;
	return father[u]=getfather(father[u]);
}
inline void judge(int x,int y)
{
	int fx=getfather(x),fy=getfather(y);
	father[fx]=fy;
}

int n,x[MAXN],y[MAXN],re;

int main()
{
	freopen("ppg.in","r",stdin);
	freopen("ppg.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d",x+i,y+i);
	for(int i=0;i<n;i++)
		father[i]=i;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			int dis=(abs(x[i]-x[j])+abs(y[i]-y[j])+1)/2;
			v.push_back(Node(dis,i,j));
		}
	sort(v.begin(),v.end());
	for(vector<Node>::iterator it=v.begin();it!=v.end();it++)
	{
		if (getfather(it->u)!=getfather(it->v))
		{		
			re=it->dis;
			judge(it->u,it->v);
		}
	}
	printf("%d\n",re);
	return 0;
}