ABC224 C - Triangle? C++解答例

AtCoder Beginner Contest 224 C - Triangle?をC++で解きます。

問題

問題文をAtCoderのサイトより引用します。

問題文

$xy$平面上に1から$N$までの番号がついた$N$個の点があります。
点$i$は座標$(X_i, Y_i)$にあり、相異なる2点は異なる2点に存在します。
この$N$点から3点選ぶとき、選ばれた3点を線分で結んだ図形が正の面積を持つ三角形になるような点の選び方の総数を求めてください。

制約

• 入力はすべて整数である
• $3 \leq N \leq 300$
• $-10^9 \leq X_i, Y_i \leq 10^9$
• $i \neq j$ならば$(X_i, Y_i) \neq (X_j, Y_j)$

解答例

選んだ3点が三角形を成さない条件

$N$個の点から3点を選んだとき、「その3点を線分で結んだ図形が正の面積を持たない」条件は、その3点が一直線上に並んでいるときとなります。
また、$N$の制約が最大で300と緩いので、$N$個の中から3点を選ぶ場合の数を全探索して、そのそれぞれに対して3点が一直線上に並んでいるか否かを判定すれば問題を解くことができます。

3点が一直線上に並んでいるかどうかを判定するには、3点のうちの2点が成す直線上に残りの1点が存在するかどうかを判定すると良いでしょう。
$N$個の中から選んだ3点をそれぞれ$(X_i, Y_i), (X_j, Y_j), (X_k, Y_k) (i < j < k)$とします。
このうち、2点$(X_i, Y_i), (X_j, Y_j)$が成す直線の式は以下のように表されます。^[1]

$$y - Y_i = \frac{Y_j - Y_i}{X_j - X_i}(x - X_i)$$

除算が絡むと誤差を考慮しなければならなくなり面倒なので、分母を払って次のように変形します。

$$(y - Y_i)(X_j - X_i) = (Y_j - Y_i)(x - X_i)$$

この式の変数$x$と$y$にそれぞれ残りの1点の座標$X_k$と$Y_k$を代入したとき、等式が成り立てば、3点は一直線上に存在するということになります。

実装例

実際のコードを示します。計算量は$\mathcal{O}(N^3)$です。

尚、それぞれの辺の積で一番大きくなる値は$(2 \times 10^9)^2 = 4 \times 10^{18}$ですが、これは符号付き64bit整数の最大値9223372036854775807より小さいのでオーバーフローを起こすことはありません。

c.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
int main() {
  int64_t N;
  std::cin >> N;
  std::vector<int64_t> x(N);
  std::vector<int64_t> y(N);
  for (int64_t i = 0; i < N; i++) {
    std::cin >> x.at(i) >> y.at(i);
  }
 
  int64_t count = 0;
  for (int64_t i = 0; i < N; i++) {
    for (int64_t j = i + 1; j < N; j++) {
      for (int64_t k = j + 1; k < N; k++) {
        if ((y.at(k) - y.at(i)) * (x.at(j) - x.at(i)) == (y.at(j) - y.at(i)) * (x.at(k) - x.at(i))) {
          continue;
        } else {
          count++;
        }
      }
    }
  }
 
  std::cout << count << std::endl;
 
  return 0;
}

実際に提出したコードはこちら。

参考文献

• 二点を通る直線の方程式の3タイプ 高校数学の美しい物語

脚注

1. https://manabitimes.jp/math/894