AtCoder Beginner Contest 181 C - Collinearity

問題

問題文へ

N個の点の中から、3点を選んで同一直線上にあるか調べてください。

制約

• 入力は整数
• 3 N
• ,
• i jならば

考えたこと

恥ずかしながら、3点が同一直線上にあるかの判定は検索しました。

3点を選ぶ組み合わせは、それほど多くないのですべて調べれば良さそうです。

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const double EPS = 1e-10;


int main(void) {
  int N;
  cin >> N;
  vector<P> v(N);
  rep(i, N) {
    cin >> v[i].first >> v[i].second;
  }

  for (int i = 0; i < N - 2; ++i) {
    for (int j = i + 1; j < N - 1; ++j) {
      for (int k = j + 1; k < N; ++k) {
        double AB = sqrt((v[i].first - v[j].first) * (v[i].first - v[j].first) +
                         (v[i].second - v[j].second) * (v[i].second - v[j].second));
        double AC = sqrt((v[i].first - v[k].first) * (v[i].first - v[k].first) +
                         (v[i].second - v[k].second) * (v[i].second - v[k].second));
        double BC = sqrt((v[j].first - v[k].first) * (v[j].first - v[k].first) +
                         (v[j].second - v[k].second) * (v[j].second - v[k].second));
        if (abs((AB + AC) - BC) < EPS ||
            abs((AB + BC) - AC) < EPS ||
            abs((AC + BC) - AB) < EPS) {
          cout << "Yes" << endl;
          return 0;
        }
      }
    }
  }

  cout << "No" << endl;
 
  return 0;
}

解説を読んで

傾きが等しいかで判定すればよいようです。これは小中学生の知識でもわかりそうです。

0除算をなくすため、乗算にしています。

除算は誤差が出る可能性もあると思いましたが、そこまで考えが至りませんでした。