题解：AT_abc422_e Colinear

Shimarin1001 · 2025-09-12 21:53:49 · 题解

提供一种不需要随机化的做法。

如果存在满足条件的直线，那么直线上的点在原数组中肯定不会距离太远。具体来讲，一定可以在这条直线上找到两个点，使这两个点在原数组中的下标差不超过 2。

求两个点确定的直线解析式是 O(1) 的，而检查一条直线是否满足条件是 O(n) 的，我们只找每个点向后的两个点，求出它们确定的直线的解析式，并用一个桶记录每个解析式的出现次数。

最终满足条件的直线一定是出现次数较多的直线，理论上只需要检查出现次数最多和次多的直线即可。