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: