The 13th Chinese Northeast Collegiate Programming Contest【C】

题意：给你一个n，接下来n行，每行四个数，分别代表x1，y1，x2，y2，即这条线过的俩个点，最后我们要求这些线段有多少个交点，记住，重叠的俩条线也算有交点，平行直线则没有交点。我们知道俩点可以确定一条直线，已知俩点我们可以求得斜率和截距 $图片说明$ 即将直线转换成y=kx+b的形式但这种形式转换会有一个问题，无法表示斜率不存在的直线，即x1-x2=0的情况，为了改善这个公式，我们采用方程俩边同时乘以(x1-x2)的方法，将除法转换成乘法，不仅保证了不会除以0，还保证了不用开double来保持高精度（因为除的时候可能会导致斜率为小数，要开double，乘的话则不用考虑这个问题）那我们的式子就转换成了 $图片说明$ 别忘了，还有一件事情要考虑，就是俩条所给的直线是一样的，但是表示出来是倍数关系导致存的时候存到了不一样的地方，即y=x和2y=2x是同一条直线，那我们就得把每条直线写成最简形式，即对于每一个斜率，我们先要求出来g=gcd（x1-x2,y1-y2）.然后分别除以g来使原式化到最简

到此，我们将直线部分处理完毕，接下来就是要存直线了，我们知道一个斜率和一个截距对应一条直线，那我们就开个map，里面套个pair再套个pair，一个是斜率（斜率我们这里用了乘法，所以要再套个pair存俩个值），一个是截距，存着就好了

存完直线，我们来考虑交点怎么处理，我们知道俩条线只要斜率不一样一定会有交点，斜率要是一样，只要截距也一样的话，也有交点。我们可以这样考虑这个问题，我们现在进来一条直线，他有多少条直线和它没有交点？那对于这条直线对ans的贡献，就是当前直线的条线减去和他平行直线的条数即可。那现在的问题就是要知道平行直线的数量，有什么比较好的方法求得这个数量呢，因为 $图片说明$ ，那我们就再开一个map，里面把所有斜率一样的直线都存进去即可最后就可以边存直线边算答案了

代码如下：

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const ll maxn=1e5+5;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; } ;
//double k[maxn];
map<pair<pair<ll,ll>,ll>,ll>same;
map<pair<ll,ll>,ll>ALL;
int main()
{
    ll _;_=read();while (_--)
    {
        ll n=read(),cnt=0,ans=0;
        same.clear();ALL.clear();
        for(ll i=1;i<=n;i++)
        {
            ll x1=read(),y1=read(),x2=read(),y2=read();
            ll tmp1=x1-x2,tmp2=y1-y2;
            //prinf("%d %d\n",tmp1,tmp2);
            ll g=__gcd(tmp1,tmp2);
            if(tmp1<0&&tmp2<0) tmp1=-tmp1,tmp2=-tmp2;
            tmp1/=g,tmp2/=g;
            //prinf("%d %d\n",tmp1,tmp2);
            ll ju=tmp1*y1-tmp2*x1;
            same[{make_pair(tmp1,tmp2),ju}]++;
            ALL[make_pair(tmp1,tmp2)]++;
            cnt++;//直线个数
            ans=ans+cnt-ALL[make_pair(tmp1,tmp2)]+same[{make_pair(tmp1,tmp2),ju}]-1;
        }
        printf("%lld\n",ans);
    }
}