Eureka
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.
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.
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
#include<cstdio> #include<iostream> #include<map> #include<cmath> #include<algorithm> #define fi first #define se second using namespace std; typedef long long LL; const int MOD=1e9+7; struct point { LL x,y; bool operator == (const point &t)const { return x==t.x&&y==t.y; } bool operator < (const point &t)const { return x==t.x?y<t.y:x<t.x; } }p[1005]; map<pair<LL,LL>,int>f; LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } pair<LL,LL> get_slope(point a,point b) { LL up=b.y-a.y; LL dw=b.x-a.x; LL t=gcd(up,dw); up/=t,dw/=t; return make_pair(up,dw); } LL quick_mod(int a,int b) { LL res=1,t=a; while(b) { if(b&1)res=(res*t)%MOD; t=(t*t)%MOD; b>>=1; } return res; } int main() { int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); LL ans=0; for(int i=0;i<n;i++) scanf("%lld%lld",&p[i].x,&p[i].y); sort(p,p+n); for(int i=0;i<n;i++) { f.clear(); int res=0; for(int j=i+1;j<n;j++) { if(p[i]==p[j])res++; else f[get_slope(p[i],p[j])]++; } (ans+=quick_mod(2,res)-1)%=MOD; for(map<pair<LL,LL>,int>::iterator iter=f.begin();iter!=f.end();iter++) (ans+=quick_mod(2,res)*(quick_mod(2,iter->se)-1))%=MOD; } printf("%lld ",ans); } } /* 1 6 -1 -1 1 -1 -1 1 1 1 0 0 0 0 25 */