## C - Triangle? Editorial by en_translator

First let us focus on the constraints.

It says \(N \le 300\), so we can predict that a solution of time complexity \(O(N^3)\) will find the correct answer fast enough.

Therefore, we can get the right answer in a sufficiently short time if we can exhaustively iterate all combinations of three points and checking each of them if they forms a triangle with a positive area in an \(O(1)\) time each.

Now, how can we determine whether some three points forms a triangle? In fact, the following formula is available.

A triangle with vertices \((x_1,y_1)\), \((x_2,y_2)\), and \((x_3,y_3)\), has the area expressed by:

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

(Note that if the value is \(0\), then the three given points are in a common line.)

This time, what matters is whether it forms a triangle or not, so it is sufficient to check if \((x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)\).

Sample code (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: