AtCoder Beginner Contest 248 E - K-colinear Line

直線上の点を数え上げる問題。本番で AC できなかったので解法をメモ

問題

AtCoder Beginner Contest 248 E - K-colinear Line

勉強になったこと

• 1 次直線をどうやって少数使わずに表現するか（同じ直線かどうかをどう判定するか）
• 直線上に点があるかの判定方法

考察

問題を見てみると、以下のようなところまではコンテスト中に割とスッと出てきた

• 頂点数が 300 なので、N³ 解法が間に合いそう
• 直線は N² で全列挙できる
• 直線を全列挙したあとに、座標が直線状にあるかを全探索すれば N³ で解ける

なので、あとは実装するだけ。めでたし、めでたし。 、、、とはなりませんでした。40 分かけてバグらせて時間切れでした、、

難しかったポイント

個人的に難しかったポイントは以下

• 「直線」を表現したいけど、普通に y=ax+b の傾き求めたら、a が少数になってしまう
• 直線全探索すると、同じ直線が出てきてしまう
• 傾きと切片を使わずに座標が直線状にあるかをどう判定すればいいのか

結果としては、以下のようにすると個人的に一番わかりやすく実装できた

• 直線は直線上の座標の集合(vector)として表現する
• 直線は set に入れて、重複除去する
• 3 点の座標が直線上にあるかは公式使って判定

上記、ひとつずつ説明する。

「直線」を表現したいけど、普通に y=ax+b の傾き求めたら、a が少数になってしまう

「直線」を表現する時、真っ先に思いつくのが、 y=ax+b の(a,b)をペアで管理する方法。ただ、これだと a を計算する時に少数になってしまうことがあって、誤差で同一直線の判定ができないとやだな、、、という感じ

これを回避する方法は、例えば a=dy/dx とすると、dx,dy の最大公約数を求めて、割っておけば同じ直線は必ず同じ dx, dy になるので、その組み合わせで管理すると重複判定ができる。

ただ、コンテスト本番はこの方針で試して、どうもバグが取り切れず時間切れだったので、もう少しシンプルな方針にする。

どうするかと言うと、「直線 = 直線上の座標の集合」 という形で表す

例えば、y=2x+5 なら {(1,7), (4, 13), (10, 25)} みたいな感じ。 ここでは説明上、(x,y)という風に管理しているが、実際の実装は座標がを保持している配列のインデックスで管理している。

直線は set に入れて、重複除去する

直線の表現方法が決まれば、重複除去は簡単。set に突っ込むだけ。

3 点の座標が直線上にあるかは公式使って判定

ある点が直線上にあるかの判定は y=ax+b が分かっていれば代入するだけだが、今回は a,b を求めないのでそれができない。 なので、公式解説に書いてある、3 点の座標を使って直線上か判定する方法を使う （どうやら直線上の点の典型らしいです）

実装

あとは、

• 直線は直線上の座標の集合(vector)として表現する
• 直線は set に入れて、重複除去する
• 3 点の座標が直線上にあるかは公式使って判定

をそのまま実装するだけ。割とシンプルな 3 重ループになる

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

// 変数宣言------------------

// 関数定義------------------
bool same(ll x1, ll y1, ll x2, ll y2, ll x, ll y) {
  return (x2 - x1) * (y - y1) == (y2 - y1) * (x - x1);
}

// メイン------------------
int main() {
  int n, k;
  cin >> n >> k;

  ll x[n];
  ll y[n];
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }

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

  set<vector<int>> line;  // 直線の集合

  // 座標i, j を通る直線を全探索
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      // 頂点を全探索して, 直線上の座標の集合をつくる
      vector<int> pos;
      for (int k = 0; k < n; k++) {
        if (same(x[i], y[i], x[j], y[j], x[k], y[k])) {
          pos.push_back(k);
        }
      }
      // 直線をsetに追加
      line.insert(pos);
    }
  }

  // k以上の頂点がある直線をカウント
  ll ans = 0;
  for (auto it = line.begin(); it != line.end(); it++) {
    if ((int)(*it).size() >= k) {
      ans++;
    }
  }
  cout << ans << endl;
}

感想

直線上の座標を判定する方法と直線を管理する方法を勉強できてよかった。 ちゃんと考察すれば、シンプルなコードになるので考察やっぱ大事。