Dowemo

to give you n points, ask for a point in all points to be collinear ( with emphasis ). How much of this collection is.


Ideas:

1. All points are ordered first, so that the vector is and the impact of the inverse vector is removed.
2. Minimize the value of the vector with a gcd to make the same vector unique.
3. Each point is discussed separately, and statistics are evaluated for the of the total answer.

( this is used when calculating contributions: Cn0 + cn1 + cn2 + cn3 +. + cnn = 2^n ).


Code:


#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("%lldn", ans);


 }


 return 0;


}











Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs