PTA L2-054 三点共线
题目分析
本题要求在给定的二维平面点集中，找出所有纵坐标 y∈{0,1,2} 并且共线的三个点。 根据直线的斜率公式，如果 (x0,0)，(x1,1)，(x2,2) 三点共线，那么它们在 y 轴上的增量相同（每次增加 1），在 x 轴上的增量也必须相同。即： x1 - x0 = x2 - x1 化简可得：x2 = 2x1 - x0。
我们只需：
- 分别记录所有 y=0 和 y=1 的点的 x 坐标。
- 将 y=2 的点的 x 坐标存入一个支持快速查找的数据结构中。
- 双重循环枚举 y=0 和 y=1 的组合，计算并验证对应的 x2 是否存在。
常见错误分析与优化策略
本题看似简单，但在限制条件上布满了陷阱。很多同学提交时会遇到 运行超时 (TLE)、内存超限 (MLE) 或者 段错误，我们来逐一攻破：
1. 内存超限 (MLE) 应对策略
本题给 C++ 编译器的内存限制非常严苛（64MB）！
如果你使用 unordered_map<int, bool> 或 set 来记录 y=2 的点，其底层红黑树或哈希表链表结点会产生庞大的空间开销，在数据量达到五万时极易爆出 64MB 的上限，导致 MLE。
解决办法：题目给出的 x 坐标范围是 [-10^6, 10^6]，跨度大约 2000000。我们可以直接开一个大小为 2×10^6+10 的普通一维 bool 数组，利用偏移量（统一加上 10^6 做下标）进行绝对的 O(1) 查找，空间占用不到 2MB，完美解决 MLE。
2. 运行超时 (TLE) 应对策略
不仅 unordered_map 常数过大会导致超时，'先存储结果，最后再一次性排序输出'的做法也会浪费大量时间！
题目要求：'首先按照 y=1 的 x 坐标升序输出；还有相同则按照 y=0 的 x 坐标升序输出'。
解决办法：我们可以先把 y=0 和 y=1 的坐标数组直接升序排列并去重。在后续的双重循环中，外层遍历 y=1 的数组，内层遍历 y=0 的数组。这样组合枚举到的答案，先后顺序天然就满足题目的输出要求！寻找到合法的 x2 后直接 cout 输出即可，省去了庞大的结构体存储开销和排序时间。
3. 段错误 (Segmentation Fault) 应对策略
很多同学改成数组偏移映射后，又遇到了段错误，这依然是关键细节：
极端情况下，如果 x1=-10^6，而 x0=10^6，由于计算公式 x2=2x1-x0，算出来的 x2=-3×10^6。
这个时候如果我们不去判断盲目访问 mp[x2 + N]，那么索引会变成 -2×10^6，C++ 数组出现负数越界访问，当场段错误崩溃。
解决办法：因为合法的点坐标永远在 [-10^6, 10^6] 以内，所以算出来的 x2 如果超出了这个范围，就不可能出现在原图里。访问数组前必须加上越界拦截：if (abs(x2) > N) continue;。
AC 参考代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
vector<int> a[2]; // 存储 y=0 和 y=1 的点坐标
bool mp[N*];
{
ios::(), cin.(), cout.();
(mp, , (mp));
n;
cin >> n;
fl = ;
( i = ; i <= n; i++){
x, y;
cin >> x >> y;
(y < ){
a[y].(x);
}{
mp[x+N]=;
}
}
(a[].(), a[].());
(a[].(), a[].());
a[].((a[].(), a[].()), a[].());
a[].((a[].(), a[].()), a[].());
( x1 : a[]){
( x0 : a[]){
x2 = x1 * - x0;
((x2) > N) ;
(mp[x2+N]){
fl = ;
cout << << x0 << << x1 << << x2 << ;
}
}
}
(!fl){
cout << ;
}
;
}
