題目：

?

這題我WA了3次，那3次是用向量求角度去重算的，不知道錯(cuò)在哪了，不得不換思路。

第4次用斜率去重一次就過(guò)了。

注意：n定義成long long，不然求C（3，n）時(shí)會(huì)溢出。

?

代碼：

#include <bits\stdc++.h> using namespace std; typedef long long ll;struct point{int x;int y; }a[2005];map <long double,int>::iterator it; int main() {ll n;cin >> n;for(int i = 0; i < n; ++i){cin >> a[i].x >> a[i].y;}int exp = 0; //表示重復(fù)的數(shù)量for(int i = 0;i < n; ++i){map <long double,int> m;//long double表示斜率，int表示數(shù)量，定義在這里是為了清空map。for(int j = i+1;j < n; ++j){long double x = a[i].x-a[j].x;long double y = a[i].y-a[j].y;if(x == 0){m[10000000]++; //10000000表示斜率不存在}else {m[y/x]++;}}for(it = m.begin();it != m.end(); ++it){if(it->second > 1){exp += it->second*(it->second-1)/2; // 斜率去重 C（2,it-second）。 }}}cout << n*(n-1)*(n-2)/6 - exp << endl; // C(3,n)-expreturn 0; } //writed by zhangjiuding.

?

總結(jié)

以上是生活随笔為你收集整理的51nod 1451 合法三角形 判斜率去重，时间复杂度O（n^2）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。