P16293 [蓝桥杯 2026 省 Java A 组] 奇怪的地图

Link: https://www.luogu.com.cn/problem/P16293

题目描述

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

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

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

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

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

输入格式

第一行包含一个正整数 $n$，表示给出的城市数量。

接下来 $n$ 行，每行包含两个整数 $x_i,y_i$，表示第 $i$ 座城市的坐标。

输出格式

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

输入输出样例 #1

输入 #1

4
0 -1
-1 -1
2 2
4 2

输出 #1

5

说明/提示

【样例说明】

这四座城市就是图中标出的四个城市。

其中，距离最远的一对城市是 $(-1,-1)$ 和 $(4,2)$。从 $(-1,-1)$ 出发，可以先向右上方方向走 3 步，到达 $(2,2)$；再沿 $X$ 方向的正方向走 2 步，到达 $(4,2)$。

这两座城市之间的最短距离为 5，所以答案是 5。

【评测用例规模与约定】

对于 $50\%$ 的评测用例，$n\le 3000$。

对于所有的评测用例，$2\le n\le 3\times 10^5$，$|x_i|,|y_i|\le 10^9$。

---

Solution

1. 题意

给了一个六边形蜂巢网络，输入若干组坐标（两个坐标轴相隔了 $120°$），求六边形坐标下距离最远的两个点的距离。

2. 分析

个人建议先好好画画图，搞清楚这个六边形网格下的坐标计算方法。

设 $A(x_A,y_A),B(x_B,y_B)$，并设坐标差值：

$$\Delta x=|x_A-x_B|\Delta y=|y_A-y_B|$$

将坐标位置补成平行四边形很容易发现 $A,B$ 两点在六边形网格下的距离是

$$d(A,B)=\max \left(\Delta x,\Delta y,|\Delta x-\Delta y|\right)$$

或者改写成便于输入处理的格式

$$d(A,B)=\underset{1\le i\le j\le n}{\max }\left(|x_i-x_j|,|y_i-y_j|,|(x_i-y_i)-(x_j-y_j)|\right)$$

所以我们只要求出：

• $x$ 坐标的极差；
• $y$ 坐标的极差；
• $(x-y)$ 的极差；

然后取他们三个的最大值，就完事了。由于这些都可以一边输入一边更新，因此时间复杂度是 $O(n)$ 而空间复杂度是 $O(1)$。

3. 代码

Java

import java.util.Scanner;

public class Main
{
    public static void main(String[] args) 
    {
        Scanner scanner = new Scanner(System.in);
        
        long n, x, y;
        long maxx, maxy, maxd;
        long minx, miny, mind;
        
        maxx = maxy = maxd = -999999999999999L;
        minx = miny = mind = 999999999999999L;
        
        n = scanner.nextLong();
        
        for (int i = 1; i <= n; i++)
        {
            x = scanner.nextLong();
            y = scanner.nextLong();
            
            maxx = Math.max(maxx, x);
            maxy = Math.max(maxy, y);
            maxd = Math.max(maxd, x - y);
            
            minx = Math.min(minx, x);
            miny = Math.min(miny, y);
            mind = Math.min(mind, x - y);
        }
        long result = Math.max(Math.max(maxx - minx, maxy - miny), maxd - mind);
        System.out.println(result);
    }
}

C++

#include <iostream>
using namespace std;

long long n, x, y, z, maxx, minx, maxy, miny, maxd, mind;

int main()
{
	maxx = maxy = maxd = -9e18;
	minx = miny = mind = 9e18;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x >> y;

		maxx = max(maxx, x);
		maxy = max(maxy, y);
		maxd = max(maxd, x - y);

		minx = min(minx, x);
		miny = min(miny, y);
		mind = min(mind, x - y);
	}
	cout << max(max(maxx - minx, maxy - miny), maxd - mind);
}

C#

using System;

class P16293
{
    static void Main()
    {
        long n, x, y;
        long maxx, maxy, maxd;
        long minx, miny, mind;
        
        maxx = maxy = maxd = -999999999999999L;
        minx = miny = mind = 999999999999999L;
        
        n = long.Parse(Console.ReadLine());
        
        for (int i = 1; i <= n; i++)
        {
            string[] input = Console.ReadLine().Split();
            x = long.Parse(input[0]);
            y = long.Parse(input[1]);
            
            maxx = Math.Max(maxx, x);
            maxy = Math.Max(maxy, y);
            maxd = Math.Max(maxd, x - y);
            
            minx = Math.Min(minx, x);
            miny = Math.Min(miny, y);
            mind = Math.Min(mind, x - y);
        }
        
        long result = Math.Max(Math.Max(maxx - minx, maxy - miny), maxd - mind);
        Console.WriteLine(result);
    }
}