Problem Description

Given some segments which are paralleled to the coordinate axis. You need to count the number of their intersection.
The input data guarantee that no two segments share the same endpoint, no covered segments, and no segments with length 0.

Input

The first line contains an integer T, indicates the number of test case.
The first line of each test case contains a number n(1<=n<=100000), the number of segments. Next n lines, each with for integers, x1, y1, x2, y2, means the two endpoints of a segment. The absolute value of the coordinate is no larger than 1e9.

Output

For each test case, output one line, the number of intersection.

Sample Input

Sample Output

Author

BUPT

Source

#include <bits/stdc++.h>

#define mp make_pair

#define pb push_back

#define met(a,b) memset(a,b,sizeof a)

#define inf 10000000

using namespace std;

typedef long long ll;

typedef pair<int,int>pii;

const int N = 4e5+;

const double eps = 1e-;

int n,sum[N],m,cnt;

ll ans;

int lazy[N],a[N],mi[N],ma[N];

struct Line{

    int u,y,z;

    Line(int u=,int y=,int z=):u(u),y(y),z(z){}

    bool operator <(const Line f)const{

        return u<f.u||u==f.u&&z<f.z;

    }

};

vector<Line>r,c,q;

void init(){

    cnt=ans=;

    met(a,);

    r.clear();c.clear();q.clear();

}

void add(int x,int num){

    for(int i=x;i<N;i+=i&(-i)){

        a[i]+=num;

    }

}

int query(int x){

    int ret=;

    for(int i=x;i>=;i-=i&(-i)){

        ret+=a[i];

    }

    return ret;

}

int main() {

    int T,x,y,xx,yy;

    scanf("%d",&T);

    while(T--){

        init();

        scanf("%d",&n);

        for(int i=;i<=n;i++){

            scanf("%d%d%d%d",&x,&y,&xx,&yy);

            mi[++cnt]=x;mi[++cnt]=xx;

            mi[++cnt]=y;mi[++cnt]=yy;

            if(x==xx){

                if(y>yy)swap(y,yy);

                c.pb(Line(x,y,yy));

            }

            if(y==yy){

                if(x>xx)swap(x,xx);

                r.pb(Line(y,x,xx));

            }

        }

        sort(mi+,mi++cnt);

        cnt=unique(mi+,mi++cnt)-mi-;

        for(int i=;i<c.size();i++){

            c[i].u=lower_bound(mi+,mi++cnt,c[i].u)-mi;

            c[i].y=lower_bound(mi+,mi++cnt,c[i].y)-mi;

            c[i].z=lower_bound(mi+,mi++cnt,c[i].z)-mi;

            q.pb(Line(c[i].u,i,));

        }

        for(int i=;i<r.size();i++){

            r[i].u=lower_bound(mi+,mi++cnt,r[i].u)-mi;

            r[i].y=lower_bound(mi+,mi++cnt,r[i].y)-mi;

            r[i].z=lower_bound(mi+,mi++cnt,r[i].z)-mi;

            q.pb(Line(r[i].y,i,));

            q.pb(Line(r[i].z,i,));

        }

        sort(q.begin(),q.end());

        for(Line s:q){

            if(s.z==)add(r[s.y].u,);

            else if(s.z==)ans+=query(c[s.y].z)-query(c[s.y].y-);

            else add(r[s.y].u,-);

        }

        printf("%lld\n",ans);

    }

    return ;

}