There are n lines l1,l2,…,ln
on the 2D-plane.
Staring at these lines, Calabash is wondering how many pairs of (i,j)
that 1≤i<j≤n and li,lj
share at least one common point. Note that two overlapping lines also share common points.
Please write a program to solve Calabash's problem.
InputThe first line of the input contains an integer T(1≤T≤1000)
, denoting the number of test cases.
In each test case, there is one integer n(1≤n≤100000)
in the first line, denoting the number of lines.
For the next n
lines, each line contains four integers xai,yai,xbi,ybi(|xai|,|yai|,|xbi|,|ybi|≤109). It means li passes both (xai,yai) and (xbi,ybi). (xai,yai) will never be coincided with (xbi,ybi).
It is guaranteed that ∑n≤106
.
OutputFor each test case, print a single line containing an integer, denoting the answer.
Example Input3 2 0 0 1 1 0 1 1 0 2 0 0 0 1 1 0 1 1 2 0 0 1 1 0 0 1 1Output
1 0 1题解:两条直线不平行必相交,若平行:若重合答案加1,否则不算。 我们用两个map来刻画直线的特性,mp1刻画a*x+b*y的直线系有多少个,mp2刻画a*x+b*y=c这一条直线有多少个。 假设当前直线与之前的线段都相交,那么我们需要减去与这条直线平行而不重合的直线。即ans+=i-1+mp2[]-mp1[].
#include<iostream> #include<cstring> #include<string> #include<queue> #include<stack> #include<algorithm> #include<stdio.h> #include<map> #include<set> using namespace std; typedef long long ll; typedef pair<ll,ll>P; typedef pair<pair<ll,ll>,ll>Pi; const int maxn=100010; map<pair<ll,ll>,ll>mp1;//两个参数a,b,代表形如a*x+b*y=c(c任意)的直线有多少个 map<pair<pair<ll,ll>,ll>,ll>mp2;//三个参数a,b,c,代表形如a*x+b*y=c的直线有多少个,即相同直线有多少个 ll cnt,ans,n; int main() { ios::sync_with_stdio(0); int T; cin>>T; while(T--){ ans=cnt=0; cin>>n; mp1.clear(),mp2.clear(); for(int i=1;i<=n;i++){ ll x1,x2,y1,y2; cin>>x1>>y1>>x2>>y2; ll a=x1-x2,b=y1-y2,c=x1*y2-x2*y1; ll g=__gcd(a,b); a/=g;b/=g;c/=g; mp1[P(a,b)]++; mp2[Pi(P(a,b),c)]++; ans+=i-1+mp2[Pi(P(a,b),c)]-mp1[P(a,b)];//假设与前i-1条边都相交,需要减去与他平行而不重合的线段 } cout<<ans<<endl; } return 0; }