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.

2

4

1 0 1 3

2 0 2 3

0 1 3 1

0 2 3 2

4

0 0 2 0

3 0 3 2

3 3 1 3

0 3 0 2

4

0

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+;

struct Node

{

    int f,x,y,y1;

    bool operator <(const Node &R)const

    {

        return (x==R.x?f<R.f:x<R.x);

    }

} a[N];

int Maxn;

int yy[N],c[N];

void add(int x,int n)

{

    for(int i=x; i<=Maxn; i+=i&-i)c[i]+=n;

}

int sum(int x)

{

    int ans=;

    for(int i=x; i>; i-=i&-i)ans+=c[i];

    return ans;

}

unordered_map<int,int>M;

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        M.clear(),memset(c,,sizeof c);

        int n,ctot=,tot=;

        scanf("%d",&n);

        for(int i=,x1,x2,y1,y2; i<n; i++)

        {

            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            if(x1==x2)

            {

                if(y1>y2)swap(y1,y2);

                a[++ctot]= {,x1,y1,y2};

                yy[++tot]=y1;

                yy[++tot]=y2;

            }

            else

            {

                if(x1>x2)swap(x1,x2);

                a[++ctot]= {,x1,y1,};

                a[++ctot]= {,x2+,y2,-};

                yy[++tot]=y1;

            }

        }

        sort(yy+,yy+tot+);

        Maxn=;

        for(int i=; i<=tot; i++)if(!M[yy[i]])M[yy[i]]=++Maxn;

        sort(a+,a+ctot+);

        long long ans=;

        for(int i=; i<=ctot; i++)

        {

            if(a[i].f)ans+=(sum(M[a[i].y1])-sum(M[a[i].y]-));

            else add(M[a[i].y],a[i].y1);

        }

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

    }

    return ;

}