题目链接

题意

给定\(n(n\leq 700)\)个点，问共线的点最多有多少个？

思路

\(O(n^3)\)：枚举两个顶点确定一条直线，再看有多少个顶点在这条直线上。讲道理会T.

\(O(n^2logn)\)：枚举一个顶点，算其他所有点与它连线的斜率，排个序，斜率相同的（排序后相邻的）就是共线的。

Code

#include <bits/stdc++.h>

#define maxn 710

using namespace std;

typedef long long LL;

int x[maxn], y[maxn];

LL k[maxn];

int gcd(int a, int b) {

    return b ? gcd(b, a%b) : a;

}

int main() {

    int n;

    scanf("%d", &n);

    for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]);

    int ans = 0;

    for (int i = 0; i < n; ++i) {

        int tot = 0;

        for (int j = i+1; j < n; ++j) {

            int dx = x[j] - x[i], dy = y[j] - y[i];

            if (dx < 0) dx = -dx, dy = -dy;

            int div = gcd(dx, dy);

            dx /= div, dy /= div;

            k[tot++] = 1LL * dx + dy * 10000;

        }

        sort(k, k+tot);

        int cnt = 0;

        for (int j = 1; j < tot; ++j) {

            if (k[j] == k[j-1]) ++cnt;

            else ans = max(ans, cnt), cnt = 0;

        }

        ans = max(ans, cnt);

    }

    printf("%d\n", ans+2);

    return 0;

}

luogu 1142 轰炸 最多共线点数的相关教程结束。