Line-line Intersection

题意：给了N条线（注意这些线有可能重合），问两条直线有交点的对数，1 3和3 1 属于同一对，两条直线重合也算有交点

解题思路：这道题有些细节是很恶心的 因为怕卡精度，所以直接用了pair存，用map套一个pair存储斜率，但是只存储斜率是不行的，因为直线有重合的情况，所以还得用map套两个pair存储k和b。y=kx+b{k=(y1-y2)/(x1-x2),b=(x2y1-x1y2)/(x2-x1)}。因为第i条直线最多和前面的i-1条直线相交，加上i-1条，减去斜率相同的条数，再加上减多的条数（k和b值都相同的）

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

#define pi acos(-1.0)
#define e exp(1.0)
typedef long long ll;
typedef pair<ll,ll> pa;
const ll maxn=1e5+7;
const ll inf=0x3f3f3f3f;
ll T,N;
map<pair<pa,pa>,int>M;//第一个pa存斜率第二个存b值
map<pa,int>Mk;//pa存斜率
inline ll read()
{
	ll x=0,flag=1;
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-')	flag=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
int main()
{
// freopen(".../.txt","w",stdout);
	ios::sync_with_stdio(false);
	T=read();
	while(T--)
	{
		M.clear();
		Mk.clear(); 
		N=read();
		ll i,j;
		ll jie=0;
		for(i=1;i<=N;i++)
		{
			ll x1,y1,x2,y2;
			x1=read(),y1=read(),x2=read(),y2=read();
			ll ka=y1-y2,kb=x1-x2;
			ll ba=x2*y1-x1*y2,bb=x2-x1;
			ll gcdk=__gcd(abs(ka),abs(kb));
			ll gcdb=__gcd(abs(ba),abs(bb));
			pa k;//存斜率 
			if(ka==0)//斜率为0
			k=make_pair(0,0);
			else if(kb==0)//斜率不存在 
			k=make_pair(inf,inf);
			else
			{
				ka/=gcdk,kb/=gcdk;
				if(ka*kb>0)
				k=make_pair(abs(ka),abs(kb));
				else
				k=make_pair(-abs(ka),abs(kb));
			}
			pa b;//存b值 
			if(ba==0)
			b=make_pair(0,0);
			else if(bb==0)//这条直线的斜率一定是不存在的 直线平行于y轴 
			b=make_pair(x1,x1);//之所以存x1的值，区分平行和重合的情况 
			else 
			{
				ba/=gcdb,bb/=gcdb;
				if(ba*bb>0)
				b=make_pair(abs(ba),abs(bb));
				else
				b=make_pair(-abs(ba),abs(bb));
			}
			jie+=(i-1-Mk[k]+M[make_pair(k,b)]);
			Mk[k]++;
			M[make_pair(k,b)]++;
		}
		cout<<jie<<endl;
	}
	return 0;
}