题解

题意分析

题目要求我们在一组平面上的整数坐标点中，找到在同一条直线上的最多点数$K$。所有点的位置互不相同，且$2 \leq N \leq 200$。我们需要通过计算，确定单条直线能覆盖的最大点数。

解题思路

1. 问题转化：要判断多个点是否共线，可以通过计算斜率来实现。对于任意两个点，可以确定一条直线，然后检查其他点是否在这条直线上。
2. 斜率计算：对于每个点，计算它与其他所有点的斜率。如果斜率相同，则这些点共线。
3. 特殊情况处理：当两个点的$x$坐标相同（即直线垂直于$x$轴）时，斜率不存在，可以用一个特殊值（如$32767$）表示。
4. 统计最大值：对每个点，统计斜率相同的点的数量，取最大值作为结果。

实现步骤

1. 输入处理：读取点的数量$N$和每个点的坐标。
2. 遍历每个点：对于每个点，计算它与其他所有点的斜率。
3. 斜率排序与统计：将斜率排序后，统计相同斜率的数量，更新最大值。
4. 输出结果：输出单条直线上能覆盖的最大点数$K$。

代码注释

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int aid[1000][2];       // 存储所有点的坐标
float xielv[1000];       // 存储斜率
 
int main(void){
    int i, j, k;
    int max, tmp;        // max记录最大值，tmp临时计数
    int n;               // 点的数量
 
    while (scanf("%d", &n) != EOF){  // 读取输入直到文件结束
        memset(aid, 0, sizeof(aid)); // 初始化数组
        for (i = 0; i < n; i++){
            scanf("%d%d", &aid[i][0], &aid[i][1]); // 读取每个点的坐标
        }
        max = 2;         // 初始最大值为2，因为至少有两个点共线
        for (i = 0; i < n - 1; i++){ // 遍历每个点
            for (j = i + 1, k = 0; j < n; j++){ // 计算当前点与其他点的斜率
                if (aid[j][0] == aid[i][0]){ // 如果x坐标相同，斜率不存在
                    xielv[k++] = 32767;      // 用32767表示垂直斜率
                }
                else{
                    xielv[k++] = (float)(aid[j][1] - aid[i][1]) / (float)(aid[j][0] - aid[i][0]); // 计算斜率
                }
            }
            sort(xielv, xielv + k); // 对斜率进行排序
            for (j = 1, tmp = 2; j <= k; j++){ // 统计相同斜率的数量
                if (xielv[j] == xielv[j - 1]){ // 如果斜率相同
                    tmp ++;                    // 临时计数加1
                    if (tmp > max){            // 更新最大值
                        max = tmp;
                    }
                }
                else{
                    tmp = 2;                  // 重置临时计数
                }
            }
        }
        printf("%d\n", max); // 输出结果
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N^2 \log N)$，其中$N$是点的数量。对于每个点，需要计算与其他点的斜率并排序。
• 空间复杂度：$O(N)$，用于存储斜率和点的坐标。