题目分析

本题要求判断两张行星地图是否描述的是同一个行星。关键点在于：行星可能绕轴旋转，因此经度会发生变化，但纬度保持不变。

核心问题：给定两组经纬度坐标点，判断是否存在一个旋转角度，使得第一组点通过经度旋转后能与第二组点完全匹配。

算法思路

核心思想：哈希 + 字符串匹配

由于纬度不变，我们可以按纬度分组处理。对于每个纬度，比较两组点在该纬度上的经度分布情况。

关键观察

1. 纬度不变性：相同的点在两张地图上必须有相同的纬度
2. 经度旋转：所有点的经度变化相同（加上一个固定的旋转角度）
3. 环形匹配：经度范围是 $[-180, 180]$，具有环形特性

算法步骤

1. 数据预处理

   • 将浮点坐标转换为整数，避免精度问题
   • 纬度映射：$[-90, 90) \rightarrow [0, 1800000]$
   • 经度映射：$[-180, 180] \rightarrow [0, 3600000]$

2. 纬度分组验证

   • 对于每个纬度，检查两张地图在该纬度上的点数是否相同
   • 如果不同，直接返回 Different

3. 经度序列匹配

   • 对于每个纬度，将经度值排序
   • 计算相邻经度的差值序列（环形处理）
   • 使用KMP算法在环形序列中匹配

4. 旋转角度统计

   • 对于每个可能的匹配位置，计算旋转角度
   • 统计每个旋转角度出现的次数
   • 如果存在某个旋转角度在所有纬度上都匹配，则返回 Same

代码详解

数据结构

const int N = 1e6 + 5;
int n, sum;
int ax[N], ay[N], bx[N], by[N], a[N], b[N], cnt[3600005], nxt[N];
vector<int> va[1800005], vb[1800005];  // 按纬度分组的经度值

核心函数 check

bool check(vector<int> vx, vector<int> vy) {
    // 空组检查
    if ((!vx.size()) && (!vy.size())) return true;
    if (vx.size() != vy.size()) return false;
    
    sum++;  // 统计纬度组数
    
    // 排序经度值
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    
    int len = vx.size();
    
    // 构建差值序列（环形处理）
    for (int i = 1; i <= len; i++) {
        if (i == len) {
            // 环形连接：最后一个点到第一个点的距离
            a[i] = vx[0] + 3600000 - vx[i - 1];
            b[i] = vy[0] + 3600000 - vy[i - 1];
        } else {
            // 相邻点的距离
            a[i] = vx[i] - vx[i - 1];
            b[i] = vy[i] - vy[i - 1];
        }
        a[i + len] = a[i];  // 复制一份用于环形匹配
    }
    
    // KMP预处理模式串
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= len; i++) {
        while (j != 0 && b[i] != b[j + 1]) j = nxt[j];
        if (b[i] == b[j + 1]) j++;
        nxt[i] = j;
    }
    
    // 在文本串中搜索模式串
    for (int i = 1, j = 0; i < len * 2; i++) {
        while (j != 0 && a[i] != b[j + 1]) j = nxt[j];
        if (a[i] == b[j + 1]) j++;
        if (j == len) {
            // 找到匹配，计算旋转角度
            int rotation = (vy[0] - vx[i - len] + 3600000) % 3600000;
            cnt[rotation]++;
        }
    }
    return true;
}

主流程

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    
    // 读取并处理第一张地图
    double x, y;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        ax[i] = floor(x * 10000 + 0.4) + 900000;      // 纬度映射
        ay[i] = floor(y * 10000 + 0.4) + 1800000;     // 经度映射
        va[ax[i]].push_back(ay[i]);
    }
    
    // 读取并处理第二张地图
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        bx[i] = floor(x * 10000 + 0.4) + 900000;
        by[i] = floor(y * 10000 + 0.4) + 1800000;
        vb[bx[i]].push_back(by[i]);
    }
    
    // 检查每个纬度
    for (int i = 0; i <= 1800000; i++) {
        if (!check(va[i], vb[i])) {
            cout << "Different" << endl;
            return 0;
        }
    }
    
    // 检查是否存在全局旋转角度
    if (*max_element(cnt, cnt + 3600005) == sum)
        cout << "Same" << endl;
    else
        cout << "Different" << endl;
    
    return 0;
}

算法正确性证明

1. 纬度验证：如果两张地图在某个纬度上的点数不同，肯定不是同一个行星
2. 经度匹配：通过差值序列的环形匹配，确保能够找到所有可能的旋转角度
3. 全局一致性：只有当某个旋转角度在所有纬度上都匹配时，才是真正的解

复杂度分析

• 时间复杂度：$O(n \log n + 3600000)$

  • 排序：$O(n \log n)$
  • KMP匹配：每个纬度组 $O(\text{len})$
  • 总体线性可接受

• 空间复杂度：$O(n + 3600000)$

  • 在题目限制范围内

样例验证

样例1

输入的两组点可以通过旋转60度相互匹配，因此输出 Same

样例2

两组点的经度分布模式不同，无法通过单一旋转匹配，因此输出 Different

该算法通过巧妙的坐标离散化和环形序列匹配，高效解决了行星地图的匹配问题。