P1661

//#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

int x[51], y[51];
int n;
struct node {
	int a, b;
	int len;
}e[2501];
int he = 0; 
int op;
int ane[51], hae = 0;
bool fp[51] = {0};

void ae(int a, int b) {
	++he;
	e[he].a = a;
	e[he].b = b;
	e[he].len = (abs(x[a]-x[b]) + abs(y[a]-y[b]) + 1)/2;
	return ;
}

bool cmp(node a, node b) {return a.len <= b.len;}

int main(){
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf("%d%d", x+i, y+i);
		op++;
		for (int j = 1; j < i; j ++) ae(i, j);
	}
	sort (e + 1, e + he + 1, cmp);
	op-=1;
	fp[e[1].a] = 1;
	while (op > 0) {
		for (int i = 1; i <= he; i ++) {
			if(fp[e[i].a] + fp[e[i].b] == 1) {
				fp[e[i].a] = 1,  fp[e[i].b] = 1; 
				++hae, ane[hae] = e[i].len;
			} 
		}
		op --;
	}
	sort (ane + 1, ane + hae + 1);
	printf("%d", ane[hae]);
	return 0;
} 

思路 ： 最小生成树

水过了几组超级简单的数据，但是还是难逃wa的命运QAQ~