题意：给你n个点，要求一个点集中所有点共线（可有重点）。问有多少的这样的集合。
思路：
1. 先将所有点排个序，这样可以保证向量都是非负的，去除相反向量带来的影响。 2. 用gcd的方式将向量的值最小化，使相同向量的唯一性。 3. 枚举每个点进行单独讨论，统计这一个点对总答案的贡献度。
（计算贡献时用到这：cn0+cn1+cn2+cn3+…+cnn=2^n）
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3+5; const int mod = 1e9+7; struct node { int x, y; bool operator < (const node &a) const { if(x == a.x) return y < a.y; else return x < a.x; } }a[maxn]; map<node, int> m; map<node, int>::iterator it; ll fac[maxn] = {1}; int main(void) { for(int i = 1; i < maxn; i++) fac[i] = fac[i-1]*2%mod; int _, n; cin >> _; while(_--) { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y); ll ans = 0; for(int i = 1; i <= n; i++) { int cc = 1; m.clear(); for(int j = i+1; j <= n; j++) { if(a[j].x == a[i].x && a[j].y == a[i].y) { cc++; continue; } int xx = a[j].x-a[i].x, yy = a[j].y-a[i].y; int gcd = __gcd(xx, yy); if(gcd) xx /= gcd, yy /= gcd; m[node{xx, yy}]++; } if(cc > 1) ans = (ans+fac[cc-1]-1)%mod; for(it = m.begin(); it != m.end(); it++) { int cnt = it->second; ans = (ans+fac[cc-1]*(fac[cnt]-1))%mod; } } printf("%lld\n", ans); } return 0; }
