Eureka

xjb推导一下可以知道best set一定是一些共线的点, 于是问题变成问有多少个子集共线. 首先, 把所有点按照 $(x, y)$ 双关键字排序, 然后枚举最左边的点 $i$ , 那么其他点 $j$ 一定满足 $j > i$ . 把在这个点右边的点都做下极角排序(按照 $frac{1}{gcd(dx, dy)}(dx, dy)$ 排序), 统计下共线的就好了. 需要注意下对重点的处理.

我没有排序，用的Hash来统计直线

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define F(i,a,b) for(int i=a;i<=b;i++)
 5 using namespace std;
 6 typedef long long LL;
 7 int t,n,mod=1e9+7;
 8 const int M=(1<<7)-1,N=1e3+7;
 9 struct E{int a,b,cnt;E *nxt;}*g[M+1],pool[N],*cur=pool;int vis[M+1],T;
10 void init_Hash(){T++,cur=pool;}
11 inline void ins(int a,int b,int cnt,E *p=NULL){
12     int u=(a*133+b)&M;
13     if(vis[u]<T)vis[u]=T,g[u]=NULL;
14     for(p=g[u];p;p=p->nxt)if(p->a==a&&p->b==b){p->cnt+=cnt;return;}
15     p=cur++,p->a=a,p->b=b,p->cnt=cnt,p->nxt=g[u],g[u]=p;
16 }
17 struct point{int x,y;}p[1001];
18 int pw[1001];
19 int main(){
20     int t;
21     scanf("%d",&t);
22     pw[0]=1;
23     F(i,1,1000)pw[i]=(pw[i-1]<<1)%mod;
24     while(t--){
25         scanf("%d",&n);
26         F(i,1,n)scanf("%d%d",&p[i].x,&p[i].y);
27         LL ans=0;
28         F(i,1,n-1){
29             int ct=0;
30             init_Hash();
31             F(j,i+1,n){
32                 if(p[i].x==p[j].x&&p[i].y==p[j].y)ct++;
33                 else{
34                     int ax=p[i].x-p[j].x,ay=p[i].y-p[j].y,gd=__gcd(abs(ax),abs(ay));
35                     ax/=gd,ay/=gd;
36                     if(ax<0)ax=-ax,ay=-ay;
37                     if(ax==0||ay==0)if(ax==0)ay=1;else ax=1;
38                     ins(ax,ay,1);
39                 }
40             }
41             int seg=0;
42             F(j,0,M)if(vis[j]==T)
43             for(E *p=g[j];p;p=p->nxt)ans=(ans+pw[p->cnt+ct]-1)%mod,seg++;
44             ans-=(1LL*(seg-1)*(pw[ct]-1))%mod;
45             ans=(ans+mod)%mod;
46         }
47         ans=(ans+mod)%mod;
48         printf("%lld
",ans);
49     }
50     return 0;
51 }

View Code