题解：UVA270 Lining Up

· · 题解

UVA270 Lining Up 题解

题目分析

给定 n 个点的坐标，我们需要找出最多有多少个点共线。

核心思路

对于每个点对 (i, j)，计算它们之间的斜率，然后检查其他点是否与这两个点共线（即斜率相同）。

用向量的方法（叉积判断共线）本质上是一样的，而且可以避免浮点数精度问题，但“斜率”对于初中生更好理解一些，本题对精度要求也不是那么高。

注意事项

  1. 输入：一定要读入时的空行。

  2. 输出：每组数据之间用空行分隔，尤其小心最后一个输出不能有两个空行，最多一个。

  3. 浮点数精度问题：用 abs(k[i][tgt] - src) <= 0.00001 来判断斜率是否相等，这里精度足够了。

  4. 多测要清空！

复杂度分析

时间复杂度：O(n^3)，其中 n \leq 700，绰绰有余。

空间复杂度：O(n^2) 存储斜率。

代码实现

#include<bits/stdc++.h>
using namespace std;

void solve(){
    double x[701], y[701], k[701][701];
    int n = 0;

    string line;
    while (getline(cin, line)) {
        if (line.empty()) break;

        stringstream ss(line);
        if (ss >> x[n+1] >> y[n+1]) {
            n++;
        }
    }

    // 计算斜率矩阵
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j) k[i][j] = INT_MIN;
            else if (x[i] == x[j]) k[i][j] = INT_MAX;//垂直时
            else k[i][j] = (y[i] - y[j]) / (x[i] - x[j]) * 1.0;
        }

    int ans = 0;
    // 检查每对点，统计共线点数
    for (int i = 1; i <= n; i++) 
        for (int j = i + 1; j <= n; j++) {
            double src = k[i][j];
            int cnt = 2;  // 至少包含i和j两个点

            for (int tgt = 1; tgt <= n; tgt++){
                if(tgt == i || tgt == j) continue;
                if (abs(k[i][tgt] - src) <= 0.00001) {
                    cnt++;
                }
            }

            ans = max(ans, cnt); 
        }

    cout << ans << endl;
}

int main(){
    int t;
    cin >> t;
    scanf("\n");  // 读取换行符

    while (t--) {
        solve();
        if(t) cout << endl;  // 组间输出空行
    }

    return 0;
}

优化思路

虽然 O(n^3) 的算法在 n \leq 700 时可以通过，但还有更优的解法，比如说进行排序，时间复杂度：O(n^2 \log n)。

代码如下：

#include<bits/stdc++.h>
using namespace std;

void solve(){
    double x[701], y[701];
    int n = 0;

    string line;
    while (getline(cin, line)) {
        if (line.empty()) break;

        stringstream ss(line);
        if (ss >> x[n] >> y[n]) {
            n++;
        }
    }

    if (n == 1) {
        cout << 1 << endl;
        return;
    }

    int ans = 0;

    for (int i = 0; i < n; i++) {
        vector<double> slopes;

        // 计算其他所有点与基准点的斜率
        for (int j = 0; j < n; j++) {
            if (i == j) continue;

            if (x[i] == x[j]) {
                slopes.push_back(INT_MAX); // 垂直线
            } else {
                double slope = (y[i] - y[j]) / (x[i] - x[j]);
                slopes.push_back(slope);
            }
        }

        // 对斜率进行排序
        sort(slopes.begin(), slopes.end());

        // 统计相同斜率的连续出现次数
        int cnt = 1;
        int mc = 1;

        for (int k = 1; k < slopes.size(); k++) {
            if (abs(slopes[k] - slopes[k-1]) <= 1e-9) {
                cnt++;
                mc = max(mc, cnt);
            } else {
                cnt = 1;
            }
        }

        // 最大共线点数 = 相同斜率的最大数量 + 1
        ans = max(ans, mc + 1);
    }

    cout << ans << endl;
}

int main(){
    int t;
    cin >> t;
    scanf("\n");  // 读取换行符

    while (t--) {
        solve();
        if(t) cout << endl;  // 组间输出空行
    }

    return 0;
}