題意：
? ? ? 給你n個點，問你3點共線的組合數有多少，就是有多少種組合是滿足3點共線的。


思路：

? ? ?一開始抱著試1試的態度，暴力了一個O(n^3),結果一如既往的超時了，然后又在剛剛超時的代碼上直接加了一個優化，就是如果當前斜率出現的次數小于2次，那么第三重for就不用在跑了，結果，呵呵，又超時了，然后又嘗試了一個方法，就是枚舉每一個點，求出所有點跟他組成的線段的斜率，記錄每個斜率出現的次數，比如當前的斜率0.5出現了8次，那么就Ans + C(8,2) 一開始寫的是C(8,3)忘記了當前的這個點必須在線段上，所以wa了一發，最后答案再除以3就行了，因為任意一組情況中的三個點都得到了一個答案，所以除以3.具體的細節看代碼。

#include<stdio.h> #include<map.h> using namespace std;typedef struct {double x ,y; }NODE;NODE node[1100]; double mkxl[1100]; map<double ,__int64>mark;double xl(int a ,int b) {if(node[a].x == node[b].x) return 1000000000.0;return (node[a].y - node[b].y) / (node[a].x - node[b].x); }int main () {int t ,n ,i ,j ;__int64 Ans;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(i = 1 ;i <= n ;i ++)scanf("%lf %lf" ,&node[i].x ,&node[i].y);Ans = 0;for(i = 1 ;i <= n ;i ++){mark.clear();int nowid = 0;for(j = 1 ;j <= n ;j ++){if(i == j) continue;if(++mark[xl(i ,j)] == 1)mkxl[++nowid] = xl(i ,j);}for(j = 1 ;j <= nowid ;j ++){__int64 tmp = mark[mkxl[j]];if(tmp >= 2)Ans += tmp * (tmp - 1) / 2;}}printf("%I64d\n" ,Ans / 3);}return 0; }

?

總結

以上是生活随笔為你收集整理的hdu 5020 求三点共线的组合数（容器记录斜率出现次数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。