【题解】直线相交

题意

给你个整点，两点之间能够形成一条直线，问所有的直线当中，相交的有多少对呢。

题解

考虑一共由多少条直线有条不同的直线，然后在考虑有多少条直线的组合呢。条直线组合，所以答案会超过范围需要开。那么考虑如何去求有多少条直线相交呢。考虑直线的一般式。若两条直线平行那么他们的就会相等，我们可以开个来映射有多少条直线是平行的。在我们遍历直线的时候，我们可以考虑这条直线的贡献是多少，为当前枚举过的直线数减去和当前这条直线平行的直线数。这是当前这条直线的贡献。这样计算每条直线的贡献就不会算重和算露了。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
map<pair<int,int>,set<int> >mp;
int x[N],y[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&x[i],&y[i]);
    long long ans = 0,cnt = 0;
    for(int i = 0;i<n;++i)
    {
        for(int j= i+1;j<n;++j)
        {
            int a = x[j] - x[i],b=y[j]-y[i],c =x[i]*y[j]-x[j]*y[i];
            int g= __gcd(a,b);
            a/=g,b/=g,c/=g;
            pair<int,int> tmp = make_pair(a,b);
            if(mp[tmp].find(c)==mp[tmp].end())
            {
                ++cnt;
                mp[tmp].insert(c);
                ans+=cnt-mp[tmp].size();
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}