题目分析本题要求找出一条直线使其覆盖平面上的点数最多。由于飞机只能沿直线飞行一次问题等价于在给定的 n 个点中找到共线点数的最大值。数据范围 n ≤ 700点数规模适中。最直接的做法是枚举任意两个点确定一条直线再统计该直线上有多少个点。枚举两点需要 O(n²)统计直线上点数需要 O(n)总复杂度为 O(n³)在 n700 时约为 3.4 亿次运算可能超时需要优化。优化思路固定一个点 i 作为基准计算它与其他所有点连线的斜率。如果多个点与点 i 的连线斜率相同说明这些点与点 i 共线。因此对于每个基准点 i统计相同斜率出现的最大次数再加上基准点本身即为经过点 i 的直线能覆盖的最多点数。枚举基准点需要 O(n)计算斜率并排序需要 O(n log n)总复杂度为 O(n² log n)在 n700 时可以轻松通过。斜率处理细节由于坐标是整数斜率可能不是整数直接使用浮点数可能产生精度误差。更稳妥的做法是使用最简分数来表示斜率即用分子和分母的最大公约数进行约分并统一符号例如规定分母为正。这样每一对 (dx, dy) 经过约分后就能唯一表示一条直线的方向。C 参考代码#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairint, int p(n); for (int i 0; i n; i) { cin p[i].first p[i].second; } int ans 1; // 至少能覆盖 1 个点 for (int i 0; i n; i) { mappairint, int, int cnt; for (int j 0; j n; j) { if (i j) continue; int dx p[j].first - p[i].first; int dy p[j].second - p[i].second; int g gcd(dx, dy); dx / g; dy / g; // 统一符号规定 dx 为正若 dx 为 0则规定 dy 为正 if (dx 0 || (dx 0 dy 0)) { dx -dx; dy -dy; } cnt[{dx, dy}]; } for (auto kv : cnt) { ans max(ans, kv.second 1); // 加上基准点 i } } cout ans endl; return 0; }复杂度分析时间复杂度为 O(n² log n)空间复杂度为 O(n)。对于 n ≤ 700 的数据范围该算法运行效率很高可以轻松通过全部测试数据。