UVA270 Lining Up 题解

题目分析

给定

n

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

核心思路

对于每个点对

(i, j)

，计算它们之间的斜率，然后检查其他点是否与这两个点共线（即斜率相同）。

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

注意事项

输入：一定要读入时的空行。
输出：每组数据之间用空行分隔，尤其小心最后一个输出不能有两个空行，最多一个。
浮点数精度问题：用 abs(k[i][tgt] - src) <= 0.00001 来判断斜率是否相等，这里精度足够了。
多测要清空！

复杂度分析

时间复杂度：

O(n^3)

，其中

n \leq 700

，绰绰有余。

空间复杂度：

O(n^2)

存储斜率。

代码实现

CPP

#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)

。

代码如下：

CPP

#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;
}

题解：UVA270 Lining Up

文章操作