Eureka

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3188    Accepted Submission(s): 899 Problem Description Professor Zhang draws n points on the plane, which are conveniently labeled by 1,2,...,n . The i -th point is at (xi,yi) . Professor Zhang wants to know the number of best sets. As the value could be very large, print it modulo 109+7 . A set P ( P contains the label of the points) is called best set if and only if there are at least one best pair in P . Two numbers u and v (u,v∈P,u≠v) are called best pair, if for every w∈P , f(u,v)≥g(u,v,w) , where f(u,v)=(xu−xv)2+(yu−yv)2−−−−−−−−−−−−−−−−−−√ and g(u,v,w)=f(u,v)+f(v,w)+f(w,u)2 .   Input There are multiple test cases. The first line of input contains an integer T , indicating the number of test cases. For each test case: The first line contains an integer n (1≤n≤1000) -- then number of points. Each of the following n lines contains two integers xi and yi (−109≤xi,yi≤109) -- coordinates of the i -th point.   Output For each test case, output an integer denoting the answer.   Sample Input 3 3 1 1 1 1 1 1 3 0 0 0 1 1 0 1 0 0   Sample Output 4 3 0

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

分析： 对于集合P满足题目的公式的话，换句话说就是P集合中的所有的点都共线。

这题的最关键点就是对与重复点和重复边的处理

先把给的这些点按坐标逆时针排序,然后按顺序选一个点i,这个点i作为一定选到集合里面的点,然后再选枚举这个点之后的点j（对于和i相同的点要特殊处理），计算出每个点j和i之间的向量存在q[]数组里面，然后使每个向量变成最简（即除以最大公约数），然后排序所有的向量那么相等的向量即在同一条直线上。

有n个元素的集合的子集的数目为2^n个

cnt记录i之后和i相同的点的数目 q[]为化简后的向量数组，q[x]~q[y]相等 所以对于这个点集合组成的集合有这些部分： 1：重点和i自身组成的集合，i算一个点，其余cnt个元素集合取出一个非空的集合即可：： pw[cnt]-1 2：在y-x个点组成的集合中取出一个非空子集:pw[y-x]-1;在cnt个重点集合中取出一个子集（可为空）:pw[cnt];两者之极即为所有组合

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<string> using namespace std; typedef long long ll; const int mod=1e9+7; ll qpow(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=(ans*a)%mod; b>>=1; a=(a*a)%mod; } return ans; } struct node1 { int x,y; }node[1010]; bool cmp(node1 p1,node1 p2) { if(p1.x!=p2.x) return p1.x<p2.x; return p1.y<p2.y; } map<pair<int ,int>,int>mapp; int main() { int t; scanf("%d",&t); while(t--) { ll ans=0; mapp.clear(); int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&node[i].x,&node[i].y); sort(node,node+n,cmp); for(int i=0;i<n-1;i++) { mapp.clear(); ll cnt=1; for(int j=i+1;j<n;j++) { if(node[i].x==node[j].x&&node[i].y==node[j].y) cnt++; else { ll x=node[i].x-node[j].x; ll y=node[i].y-node[j].y; ll g=__gcd(x,y); if(g) { x/=g; y/=g; } mapp[make_pair(x,y)]++; } } if(cnt>1) { ans=(ans+(qpow(2,cnt-1)-1)%mod)%mod; } for(map<pair<int,int>,int>::iterator it=mapp.begin();it!=mapp.end();it++) { ll sum=(ll)it->second; ans=(ans+(((qpow(2,sum)-1)*(qpow(2,cnt-1)))%mod))%mod; } } printf("%lld\n",ans); } return 0; }