题目链接：hdu_5738_Eureka
题意：
这题感觉说不清楚，坑点有点坑，一不小心就会推出错误的公式，然后最重要的是你还不知道你推错了
题解：
这里贴一个官方的题解
Eureka
xjb推导一下可以知道best set一定是一些共线的点, 于是问题变成问有多少个子集共线. 首先, 把所有点按照(x,y)(x,y)双关键字排序, 然后枚举最左边的点ii, 那么其他点jj一定满足j > ij>i. 把在这个点右边的点都做下极角排序(按照\frac{1}{gcd(dx, dy)}(dx, dy)gcd(dx,dy)1(dx,dy)排序), 统计下共线的就好了. 需要注意下对重点的处理.
我没有排序，用的Hash来统计直线
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long LL;
int t,n,mod=1e9+;
const int M=(<<)-,N=1e3+;
struct E{int a,b,cnt;E *nxt;}*g[M+],pool[N],*cur=pool;int vis[M+],T;
void init_Hash(){T++,cur=pool;}
inline void ins(int a,int b,int cnt,E *p=NULL){
int u=(a*+b)&M;
if(vis[u]<T)vis[u]=T,g[u]=NULL;
for(p=g[u];p;p=p->nxt)if(p->a==a&&p->b==b){p->cnt+=cnt;return;}
p=cur++,p->a=a,p->b=b,p->cnt=cnt,p->nxt=g[u],g[u]=p;
}
struct point{int x,y;}p[];
int pw[];
int main(){
int t;
scanf("%d",&t);
pw[]=;
F(i,,)pw[i]=(pw[i-]<<)%mod;
while(t--){
scanf("%d",&n);
F(i,,n)scanf("%d%d",&p[i].x,&p[i].y);
LL ans=;
F(i,,n-){
int ct=;
init_Hash();
F(j,i+,n){
if(p[i].x==p[j].x&&p[i].y==p[j].y)ct++;
else{
int ax=p[i].x-p[j].x,ay=p[i].y-p[j].y,gd=__gcd(abs(ax),abs(ay));
ax/=gd,ay/=gd;
if(ax<)ax=-ax,ay=-ay;
if(ax==||ay==)if(ax==)ay=;else ax=;
ins(ax,ay,);
}
}
int seg=;
F(j,,M)if(vis[j]==T)
for(E *p=g[j];p;p=p->nxt)ans=(ans+pw[p->cnt+ct]-)%mod,seg++;
ans-=(1LL*(seg-)*(pw[ct]-))%mod;
ans=(ans+mod)%mod;
}
ans=(ans+mod)%mod;
printf("%lld\n",ans);
}
return ;
}