直線状の点 [パソコン甲子園2018 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0388

考察過程

1. 制約を見るとN^2はいけるので、2点を結ぶ全ての直線は列挙できる
2. ここからK個以上の同じ点が同じ直線上に存在することを判定できないか考える
3. 同じ直線状にあるならば、同じ直線がたくさん出てくるはず
4. 全ての直線のうち、最もよく出てくる直線を探して、それがK個以上からできているかを判定すればいい？
5. それはできそう

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0388/judge/3162293/C++14

2つの頂点a,bの直線を作るが、ハッシュ値のように完全に特定できるようにする
ya = a * xa + b
yb = a * xb + b
を変形すると、
a = (ya - yb) / (xa - xb)
b = (xa * yb - xb * ya) / (xa - xb)
となる。これで割ってdoubleを求めてmapに入れて個数をカウントする。
としたい所だが、これをしたらMLEした。
なので、vectorに入れてソートして隣り合う同じ要素を数えることにしよう。
後は、最大の個数についてK(K-1)/2以上であれば、1が答え。
　
これで良さそうだが、xa=xbの場合は0で割ることになってしまう。
なので、縦に連なる点については別に考えることにしよう。
cnt2[x] := x座標がxである点の個数
これでK以上のものがあるか判定。
あれば1が答え。
　
この2つの判定に通れば0が答え。
doubleでの比較は誤差が心配だが、この問題は通る。
やばい人がテストケースを作ったら多分落ちる。

int N, K, X[3010], Y[3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> X[i] >> Y[i];

    vector<pair<double, double>> cnt;
    rep(a, 0, N) rep(b, a, N) if(X[a] != X[b]) {
        int a_up = Y[a] - Y[b];
        int a_dn = X[a] - X[b];

        int b_up = (X[a] * Y[b] - X[b] * Y[a]);
        int b_dn = X[a] - X[b];

        double aa = 1.0*a_up / a_dn;
        double bb = 1.0*b_up / b_dn;

        cnt.push_back({ aa, bb });
    }
    sort(all(cnt));

    int ma = 0;
    rep(i, 0, cnt.size()) {
        int found = 0;
        rep(j, i + 1, cnt.size()) if (cnt[i] != cnt[j]) {
            chmax(ma, j - i);
            i = j - 1;
            found = 1;
            break;
        }
        if (!found) {
            chmax(ma, (int)cnt.size() - i);
            break;
        }
    }

    int Kma = K * (K - 1) / 2;
    if (Kma <= ma) {
        printf("1\n");
        return;
    }

    map<int, int> cnt2;
    rep(i, 0, N) cnt2[X[i]]++;
    fore(p, cnt2) if (K <= p.second) {
        printf("1\n");
        return;
    }

    printf("0\n");
}