Official

C - Triangle? Editorial by physics0523


まず、この問題の制約に着目しましょう。
\(N \le 300\) とあるので、この問題は時間計算量 \(O(N^3)\) の解法をとると十分高速に正解できることが予想されます。
つまり、 \(3\) 点の選び方を全探索して、選んだ \(3\) 点を結んで正の面積をもつ三角形になるかどうかを \(O(1)\) で判定することができれば、十分高速にこの問題に正解できるということになります。

では、 \(3\) 点が三角形になるかをどのように判定すればよいでしょうか。実は、以下の公式を利用することが出来ます。

\(3\)\((x_1,y_1),(x_2,y_2),(x_3,y_3)\) を結んで出来る三角形の面積は、以下の式で表される。

\(\frac{1}{2}\ |(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)|\)

(但し、 この値が \(0\) になる場合は \(3\) 点が一直線上にある。)

なお、今回重要なのは三角形をなすかどうかなので、 \((x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)\)\(0\) かどうかだけを判断すればよいです。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<pair<long long,long long>> p(n);
  for(auto &nx : p){cin >> nx.first >> nx.second;}
  int res=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      for(int k=j+1;k<n;k++){
        if((p[j].first-p[i].first)*(p[k].second-p[i].second)-(p[k].first-p[i].first)*(p[j].second-p[i].second)!=0){res++;}
      }
    }
  }
  cout << res << '\n';
}

posted:
last update: