L2-054 三点共线 (C++ 题解与易错坑点分析)

Ne0inhk

— 5 min read

PTA L2-054 三点共线 (C++ 题解与易错坑点分析)

题目分析

本题要求在给定的二维平面点集中，找出所有纵坐标 y∈{0,1,2}y \in \{0, 1, 2\}y∈{0,1,2} 并且共线的三个点。
根据直线的斜率公式，如果 (x0,0)(x_0, 0)(x0​,0)，(x1,1)(x_1, 1)(x1​,1)，(x2,2)(x_2, 2)(x2​,2) 三点共线，那么它们在 yyy 轴上的增量相同（每次增加 1），在 xxx 轴上的增量也必须相同。即：
x1−x0=x2−x1x_1 - x_0 = x_2 - x_1x1​−x0​=x2​−x1​
化简可得：x2=2x1−x0x_2 = 2x_1 - x_0x2​=2x1​−x0​。

我们只需：

  1. 分别记录所有 y=0y=0y=0 和 y=1y=1y=1 的点的 xxx 坐标。
  2. 将 y=2y=2y=2 的点的 xxx 坐标存入一个支持快速查找的数据结构中。
  3. 双重循环枚举 y=0y=0y=0 和 y=1y=1y=1 的组合，计算并验证对应的 x2x_2x2​ 是否存在。

从“段错误、TLE、MLE”到 AC 的踩坑日记

这题看似简单，但在限制条件上布满了陷阱。很多同学提交时会遇到 运行超时 (TLE)、内存超限 (MLE) 或者 段错误，我们来逐一攻破：

1. 内存超限 (MLE) 应对策略

本题给 C++ 编译器的内存限制非常严苛（64MB）！
如果你使用 unordered_map<int, bool> 或 set 来记录 y=2y=2y=2 的点，其底层红黑树或哈希表链表结点会产生庞大的空间开销，在数据量达到五万时极易爆出 64MB 的上限，导致 MLE。
解决办法：题目给出的 xxx 坐标范围是 [−106,106][-10^6, 10^6][−106,106]，跨度大约区区 200000020000002000000。我们可以直接开一个大小为 2×106+102\times 10^6 + 102×106+10 的普通一维 bool 数组，利用偏移量（统一加上 10610^6106 做下标）进行绝对的 O(1)O(1)O(1) 查找，空间占用不到 2MB，完美解决 MLE。

2. 运行超时 (TLE) 应对策略

不仅 unordered_map 常数过大会导致超时，“先存储结果，最后再一次性排序输出”的做法也会浪费大量时间！
题目要求：“首先按照 y=1y = 1y=1 的 xxx 坐标升序输出；还有相同则按照 y=0y = 0y=0 的 xxx 坐标升序输出”。
解决办法：我们可以先把 y=0y=0y=0 和 y=1y=1y=1 的坐标数组直接升序排列并去重。在后续的双重循环中，外层遍历 y=1y=1y=1 的数组，内层遍历 y=0y=0y=0 的数组。这样组合枚举到的答案，先后顺序天然就满足题目的输出要求！寻找到合法的 x2x_2x2​ 后直接 cout 输出即可，省去了庞大的结构体存储开销和排序时间。

3. 段错误 (Segmentation Fault) 应对策略

很多同学改成数组偏移映射后，又遇到了段错误，这依然是魔鬼细节：
极端情况下，如果 x1=−106x_1 = -10^6x1​=−106，而 x0=106x_0 = 10^6x0​=106，由于计算公式 x2=2x1−x0x_2 = 2x_1 - x_0x2​=2x1​−x0​，算出来的 x2=−3×106x_2 = -3 \times 10^6x2​=−3×106。
这个时候如果我们不去判断盲目访问 mp[x2 + N]，那么索引会变成 −2×106-2 \times 10^6−2×106，C++ 数组出现负数越界访问，当场段错误崩溃。
解决办法：因为合法的点坐标永远在 [−106,106][-10^6, 10^6][−106,106] 以内，所以算出来的 x2x_2x2​ 如果超出了这个范围，就不可能出现在原图里。访问数组前必须加上越界拦截：if (abs(x2) > N) continue;。

最终满分 AC 代码

#include<bits/stdc++.h>usingnamespace std;constint N=1e6; vector<int> a[2];// 开到 200多万，足够容纳 x ∈ [-100w, 100w] 偏移后的下标bool mp[N*2+10];signedmain(){// 解除同步，大幅提升 cin/cout 速度 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);memset(mp,0,sizeof(mp));int n; cin >> n;bool fl =0;// 标记是否有解for(int i =1; i <= n; i++){int x, y; cin >> x >> y;if(y <2){ a[y].push_back(x);}else{// 对于 y=2 的点，映射到 mp 数组，加 N (10^6) 防止负数下标 mp[x+N]=1;}}// 对参与枚举的 a[0] 和 a[1] 升序排序并去重sort(a[0].begin(), a[0].end());sort(a[1].begin(), a[1].end()); a[0].erase(unique(a[0].begin(), a[0].end()), a[0].end()); a[1].erase(unique(a[1].begin(), a[1].end()), a[1].end());// 按照题目输出顺序要求：先 y=1 升序，所以外层循环是 x1for(auto x1 : a[1]){for(auto x0 : a[0]){int x2 = x1 *2- x0;// 越界拦截！防止产生的奇葩极限数值去访问数组引发段错误if(abs(x2)> N)continue;if(mp[x2+N]){ fl =1; cout <<"["<< x0 <<", 0] ["<< x1 <<", 1] ["<< x2 <<", 2]\n";}}}if(!fl){ cout <<"-1";}return0;}

复杂度总结

  • 时间复杂度：去重排序 O(nlog⁡n)O(n \log n)O(nlogn)，双重循环最坏情况约 2.5×104⋅2.5×104=6.25×1082.5 \times 10^4 \cdot 2.5 \times 10^4 = 6.25 \times 10^82.5×104⋅2.5×104=6.25×108 次常数极小的判断。总耗时远小于 2000ms 的限制，几乎瞬间跑完。
  • 空间复杂度：mp 占有不到 2MB，vector 占有数 MB，整体轻松满足 64MB 限制条件。完美谢幕！
Could not load content