/ WHOJ / 题库 /

起义

起义

描述

因为周幽王管理不当,引起了nn个村庄的不满。这nn个村庄开始起义。现在nn个村庄商量好连在一起,扩大地盘。每个村庄分布在如下图所示的棋盘格式的地图中某些行列交叉的位置,现在给出每个村庄的坐标,每个村的村长从自己村开始往外攻占地盘,每天可以向四周各扩散一个位置,当两个村某天扩散到同一个交叉点位置时,说明这两个村的地盘就通了,但是只要还剩11个村没有联通,其他村就会一直这样打下去,那么多少天之后所有村的地盘都能连通起来?

格式

输入格式

输入第11行一个整数nn,表示共有nn个村庄
接下来nn行,每行两个整数xiyix_i,y_i,表示第ii个村庄的坐标。

输出格式

输出一行一个整数,表示让所有村庄都能连通的天数。

样例1

输入样例1

2
1 1
6 6

输出样例1

限制

对于100100%的数据,满足1N50;1xi,yi1091≤N≤50; 1≤x_i,y_i≤10^9

来源

地址:vijosvijos,芜湖OIOI团队
作者:黑暗路西法0808
模拟赛T2T2