nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

hdu5738

题目核心 :对二维平面的点按照直线计数，等价于计算出每一条直线上的点的个数
        

枚举起点，再枚举终点，对斜率用map计数，可以优化常数，不要用double，会丢失精度，考虑到斜率不参与加减运算，可以用分数形式储存。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int MOD=1e9+7;
ll qpow2[2000];

void initpow(){
    qpow2[0]=1;
    for(int i=1;i<2000;i++){
        qpow2[i]=2*qpow2[i-1]%MOD;
    }
}

map<pll,int>mp;

ll x[2000],y[2000];


ll __gcd(ll a,ll b){
    return a==0?b:__gcd(b%a,a);
}

int main(){
    initpow();
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        
        for(int i=0;i<n;i++){
            scanf("%lld%lld",x+i,y+i);
        }
        
        ll ans=0;
        for(int i=0;i<n;i++){
            mp.clear();
            ll tem=0;
            for(int j=i+1;j<n;j++){
                if(x[i]==x[j]&&y[i]==y[j]){
                    tem++;
                }
                else{
                    ll gcd=__gcd(y[i]-y[j],x[i]-x[j]);
                    mp[pll((y[i]-y[j])/gcd,(x[i]-x[j])/gcd)]++;
                }
            }
            
            ans+=qpow2[tem]-1+MOD;
            ans%=MOD;
            
            for(auto x:mp){
                ans+=(qpow2[x.second]-1+MOD)*qpow2[tem];
                ans%=MOD;
            }
        }
        
        printf("%lld\n",ans);
    }
}