【题意】

给你一些二维的点，判断多少个集合中存在一个好的点对，好的点对的定义为对于集合中任何一个点w(w≠u,w≠v)，对于集合中的u，v都满足g(u,v,w)≥f(u,v)+f(u,w)+f(v,w)2。我们将式子化简一下为

f(u,v)>=f(u,w)+f(v,w)
我们知道两点之间线段最短，所以这个式子就是
f(u,v)=f(u,w)+f(v,w)
满足这个条件的集合个数，可以明显的看出这个集合中的所有的点一定是共线的，如果共线的点数为n，那么集合数目就是
ans=C(n2)+C(n3)+C(n4)+⋯+C(nn)=2n−1−n
如何处理出共线的点的数目？

【解题方法】

用map来记录对应斜率的线段的点的个数，然后枚举点，对每个点用map存下和这个店斜率相等的所有点，还有不要忘记最后处理这个点单独为重点的情况。

【AC code】


#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn=1010;
const int mod=1e9+7;
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
struct node{
    ll x,y;
    node(){}
    node(ll x,ll y):x(x),y(y){}
    bool operator <(const node &a)const{
        return x==a.x?y<a.y:x<a.x;
    }
    bool operator ==(const node &a)const{
        return (x==a.x&&y==a.y);
    }
    node operator -(const node &a)const{
        return node(x-a.x,y-a.y);
    }
    node operator *(const ll &a)const{
        return node(x*a,y*a);
    }
    node operator /(const ll &a)const{
        return node(x/a,y/a);
    }
}p[maxn];
int cnt[maxn];//统计重点数量
ll mi[maxn];//预处理二分幂
map<node,ll>mp;//记录每一个对应斜率对应的点数
ll ans;//记录答案
void init(){
    memset(cnt,0,sizeof(cnt));
    mi[0]=1;
    for(int i=1; i<=1000; i++) mi[i]=(mi[i-1]*2)%mod;
}
int main()
{
    init();
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(cnt,0,sizeof(cnt));
        cnt[0]=1;
        for(int i=0; i<n; i++) scanf("%I64d%I64d",&p[i].x,&p[i].y);
        int m=0;
        sort(p,p+n);
        for(int i=1; i<n; i++){
            if(p[m]==p[i]) cnt[m]++;
            else{
                p[++m]=p[i];
                cnt[m]++;
            }
        }
        node now;
        ans=0;
        if(m==0){
            ans=mi[cnt[0]]-1-cnt[0];
            printf("%I64d\n",ans);
            continue;
        }else{
            for(int i=0; i<=m; i++){
                mp.clear();
                for(int j=i+1; j<=m; j++){
                    now=p[i]-p[j];
                    //统一向量
                    if(now.x<0) now=now*(-1);
                    //向量化简
                    ll g=gcd(abs(now.x),abs(now.y));
                    now=now/g;
                    mp[now]+=cnt[j];
                }
                //在起点中选出至少一个数和共线的至少选出一个数组合
                for(auto it=mp.begin(); it!=mp.end(); it++){
                    ans=(ans+(((mi[cnt[i]]-1)*(mi[it->second]-1))%mod)%mod)%mod;
                }
                //处理重点
                ans=(ans+(mi[cnt[i]]-1-cnt[i]))%mod;
            }
            printf("%I64d\n",ans);
        }
    }
}