b275 - 数三角形
題目描述
題目要求計算給定平面上 n 個點所能構成的三角形數量。三角形必須是非退化的，即三點不能共線。
解題思路
此題採用暴力解法。對於任意三個點，檢查它們是否共線。如果三個點不共線，則構成一個三角形，計數器加一。由於題目保證任意兩個點不重合，因此只需要檢查三個點是否共線即可。共線的判斷方式是利用斜率。如果三個點 (x1, y1), (x2, y2), (x3, y3) 共線，則 (y2 - y1) / (x2 - x1) = (y3 - y1) / (x3 - x1)。為了避免除以零的錯誤，可以改寫為 (y2 - y1) * (x3 - x1) = (y3 - y1) * (x2 - x1)。
複雜度分析
- 時間複雜度: O(n^3)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main() {
int m, xs[100], ys[100], counts = 0;
cin >> m >> xs[0] >> ys[0] >> xs[1] >> ys[1];
for (int i = 2; i < m; ++i) {
cin >> xs[i] >> ys[i];
for (int j = 0; j < i; ++j){
int yis=ys[i]-ys[j],xis=xs[i]-xs[j];
for (int k = j + 1; k < i; ++k)
if ((yis) * (xs[i] - xs[k]) != (ys[i] - ys[k]) * (xis))
++counts;
}
}
cout << counts << '\n';
}