Dowemo
0 0 0 0

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