算法
(几何) $O(N^3)$
若存在三点共线则显然不能构成三角形,其余情况都可以
判断三点共线的充要条件:
$(x_i, y_i), (x_j, y_j), (x_k, y_k)$ 三点共线 $\Leftrightarrow$ $\frac{y_j - y_i}{x_j - x_i} = \frac{y_k - y_i}{x_k - x_i}$ $\Leftrightarrow$ $(x_j - x_i) \cdot (y_k - y_i) = (x_k - x_i) \cdot (y_j - y_i)$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> x(n), y(n);
rep(i, n) cin >> x[i] >> y[i];
int ans = 0;
rep(i, n)rep(j, i)rep(k, j) {
ll xa = x[j] - x[i];
ll ya = y[j] - y[i];
ll xb = x[k] - x[i];
ll yb = y[k] - y[i];
if (xa * yb != xb * ya) ++ans;
}
cout << ans << '\n';
return 0;
}