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: