<span>gym-102307 A. Amazon</span>

题意

给定\(n\)个点对，每个点对\((x1,y1),(x2,y2)\)确定一条直线，问这\(n\)条直线在二维平面中构成了多少个“十字路口”，若两条直线垂直相交，交点即为一个十字路口，多个重合的交点算做一个十字路口。

分析

根据直线方程的一般式\(y=kx+b\)，其中\(k=\frac{\Delta y}{\Delta x}\)，\(b=\frac{x1*y2-y1*x2}{\Delta x}\)。将直线分为三类：

• \(\Delta x=0\)即\(x1=x2\)，根据\(x1\)来去重，用\(c1\)来记录该类直线数量。
• \(\Delta y=0\)即\(y1==y2\)，根据\(y1\)来去重，用\(c2\)来记录该类直线数量。
• \(\Delta x\ne 0~and~\Delta y\ne 0\)，用分数类分别存\(k,b\)，为了去重将分数通分并且将带有负号的分数的负号放在分子上，根据\((k,b)\)来去重，用\(cnt[k]\)来记录斜率为\(k\)的直线数量。

第一类直线和第二类直线一定垂直，交点数即\(c1*c2\)，第三类直线中依据若两条直线垂直则斜率相乘为\(-1\)，所以斜率为\(\frac{\Delta y}{\Delta x}\)的直线和斜率为\(-\frac{\Delta x}{\Delta y}\)的直线垂直，统计一下就好。

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int T,n;
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int sign(int x){
    return (x>0)-(x<0);
}
pii up(pii a){
    int s=sign(a.fi)*sign(a.se);
	int g=gcd(abs(a.fi),abs(a.se));
	a.fi=s*abs(a.fi)/g;
	a.se=abs(a.se)/g;
	return a;
}
map<pair<pii,pii>,int>vis;
map<pii,int>cnt;
map<int,int>visx,visy;
int c1,c2;
int main(){
	ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>T;
	while(T--){
		cin>>n;
		vis.clear();
		cnt.clear();
		visx.clear();
		visy.clear();
		c1=c2=0;
		ll ans=0;
		for(int i=1,x1,y1,x2,y2;i<=n;i++){
			cin>>x1>>y1>>x2>>y2;
			if(x1==x2){
				if(visx.count(x1)) continue;
				visx[x1]=1;
				++c1;
			}else if(y1==y2){
			    if(visy.count(y1)) continue;
			    visy[y1]=1;
			    ++c2;
			}else{
				pii k=up(mp(y1-y2,x1-x2));
				pii b=up(mp(x1*y2-y1*x2,x1-x2));
				if(vis.count(mp(k,b))) continue;
				vis[mp(k,b)]=1;
				cnt[k]++;
                ans+=cnt[mp(-1*k.se,k.fi)];
                ans+=cnt[mp(k.se,-1*k.fi)];
			}
		}
		cout<<ans+1ll*c1*c2<<'\n';
	}
	return 0;
}