AtCoder Beginner Contest 248 E - K-colinear Line // 计算几何

原题链接：E - K-colinear Line (atcoder.jp)

题意：

给出直角坐标系上N个点(N <= 300)，求经过这些点中至少K个点的直线数量，若有无穷多条，则输出"Infinity"。

思路：

• 两点确定一条直线：

  当K=1时，答案自然是无穷多条。

  当K >= 2时，我们可以枚举两点，求出其确定的直线，再枚举所有点，判断该直线经过的点数是否不少于K。

• 求直线方程：用直线的一般式方程Ax+By+C=0（普适性）来表示直线。

  已知经过点（x1，y1），（x2，y2），那么A = y2 - y1, B = x1 - x2, C = x2 * y1 - x1 * y2。

  为了方便直线的判重，对参数进行处理（唯一性），使得：ABC三数公因数为1，A > 0 或 A = 0 且 B > 0。

代码参考：

//Jakon：计算几何
#include 
#define int long long
using namespace std;

const int N = 310;

int n, k, x[N], y[N];
setint,3>> S;

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

signed main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];

    if(k == 1) {
        cout << "Infinity" << endl;
        return 0;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            // A = y2 - y1, B = x1 - x2, C = x2 * y1 - x1 * y2
            int A = y[j] - y[i], B = x[i] - x[j];
            int C = x[j] * y[i] - x[i] * y[j];
            int g = gcd(gcd(A, B), C);
            A /= g, B /= g, C /= g;
            if(A < 0 || A == 0 && B < 0) {
                A = -A, B = -B, C = -C;
            }
            int cnt = 0;
            for(int k = 1; k <= n; k++) {
                if(A * x[k] + B * y[k] + C == 0) ++ cnt;
            }
            if(cnt >= k) S.insert({A, B, C});
        }
    }
    cout << S.size() << endl;

    return 0;
}