蓝桥杯2026年第十七届省赛真题-奇怪的地图

小蓝正在某个国家旅游。这个国家的城市分布在一个六边形网格上，如图 所示。图中的每个六边形表示一座城市。

如果两座城市有一条公共边，那么小蓝可以从其中一座城市一步走到另一 座城市。 

对于任意两座城市，若从一座城市到另一座城市至少需要走 k 步，则称这 两座城市之间的距离为 k。也就是说，这里的距离定义为两座城市之间的最少 步数。 

每座城市都可以用一个唯一的坐标 (x, y) 表示。其含义是：从坐标为 (0, 0) 的城市出发，先沿 X 方向走 x 步，再沿 Y 方向走 y 步，就可以到达该城市。

现在给出 n 座城市的坐标。你需要求出这 n 座城市中，距离最远的两座城 市之间的距离。

第一行包含一个正整数 n，表示给出的城市数量。 接下来 n 行，每行包含两个整数 xi , yi，表示第 i 座城市的坐标。

输出一行，包含一个整数，表示给出的 n 座城市中距离最远的两座城市之 间的距离。

【样例说明】 

这四座城市就是图中标出的四个城市。 其中，距离最远的一对城市是 (−1, −1) 和 (4, 2)。从 (−1, −1) 出发，可以先 向右上方向走 3 步，到达 (2, 2)；再沿 X 方向的正方向走 2 步，到达 (4, 2)。 这两座城市之间的最短距离为 5，所以答案是 5。 

【评测用例规模与约定】 

对于 50% 的评测用例，n ≤ 3000。 对于所有的评测用例，2 ≤ n ≤ 3 × 10⁵，|xi |, |yi | ≤ 10⁹。