Contest Duration: - (local time) (100 minutes) Back to Home

## 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: