1432 - Overlapping Sticks_WA_nofraction

#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
typedef long long DT;
#define MP make_pair
typedef long long LLI;
#define REP(i,n) for(int i=0;i<n;i++)
#define PB push_back
#define SORT(x) sort(x.begin(),x.end())
template<class T> inline T gcd(T a, T b)
{
    if (a < 0)return gcd(-a, b);
    if (b < 0)return gcd(a, -b);
    return (b == 0) ? a : gcd(b, a % b);
}

struct Point
{
    DT x,y;
    Point() {}
    Point(DT _x,DT _y)
    {
        x=_x;
        y=_y;
    }
};

struct Line
{
    Point st,ed;
    Line() {}
    Line(Point _x,Point _y)
    {
        st=_x;
        ed=_y;
    }
    void show()
    {
        cout << st.x << " " << st.y << endl;
        cout << ed.x << " " << ed.y << endl;
    }
};

long long inf = 100000000LL;
long long INF = 100000000LL;
Line xaxis=Line(Point(-INF,0),Point(INF,0));

pair<DT,DT> LineLineIntersection(Line A,Line B)
{
    DT A1 = A.ed.y-A.st.y;
    DT B1 = A.st.x-A.ed.x;
    DT C1 = A1*A.st.x+B1*A.st.y;

    DT A2 = B.ed.y-B.st.y;
    DT B2 = B.st.x-B.ed.x;
    DT C2 = A2*B.st.x+B2*B.st.y;

    DT det=A1*B2 - A2*B1;

    if(det == 0)
    {
        return MP(INF,INF);
        //Lines are parallel
    }
    else
    {
        double x,y;
        DT ra=0,rb=0;
        if((B2*C1 - B1*C2)==0)
        {
            x=0;
            ra=0,rb=1;
        }
        else
        {
            x = ((B2*C1 - B1*C2)*(1.0))/det;
            ra=(B2*C1 - B1*C2);
            rb=det;
        }

        if((A1*C2 - A2*C1)==0)y=0;
        else y = ((A1*C2 - A2*C1)*(1.0))/det;

        if(ra && rb)
        {
            DT g=gcd(ra,rb);
            ra/=g;
            rb/=g;
        }
        return MP(ra,rb);
    }
}

struct Z
{
    Line a;
    DT dx,dy;
    pair<DT,DT> x;// where line obect intersect X axis
    Z() {}
    Z(Line _l)
    {
        a=_l;
        dy=a.ed.y-a.st.y;
        dx=a.ed.x-a.st.x;
        if(dy && dx)
        {
            DT g=__gcd(abs(dx),abs(dy));
            dx/=g;
            dy/=g;
        }
        x=LineLineIntersection(xaxis,a);
    }
    bool friend operator < (Z A, Z B)
    {
//        if(A.dy*B.dx==A.dx*B.dy)
//        {
//            return (A.x.first*B.x.second<A.x.second*B.x.first);
//        }
//        return A.dy*B.dx<A.dx*B.dy;// lines are not paralel

        if((A.x.first*B.x.second==A.x.second*B.x.first))
        {
            return A.dy*B.dx<A.dx*B.dy;
        }
        return A.x.first*B.x.second<A.x.second*B.x.first;
    }
};

vector<Z>V;

bool same(Z A, Z B)
{
    return (A.dy*B.dx==B.dy*A.dx);
}

bool CoLine(Z A ,Z B)
{
    return (A.x.first*B.x.second==A.x.second*B.x.first);
}

struct P
{
    Point cp;
    int type;
    P() {}
    P(Point _cp,int _t)
    {
        cp=_cp;
        type=_t;
    }
    bool friend operator < (P A, P B)
    {
        if(A.cp.x==B.cp.x && A.cp.y==B.cp.y)
        {
            return A.type<B.type;
        }
        if(A.cp.x==B.cp.x)return  A.cp.y<B.cp.y;
        return A.cp.x<B.cp.x;
    }
};

Z Arg[100009];
int sza;
LLI solve()
{
    if(sza<=1)return 0;
    vector<P>tmp;
    REP(i,sza)
    {
        tmp.PB(P(Arg[i].a.st,1));
        tmp.PB(P(Arg[i].a.ed,-1));
    }
    SORT(tmp);

    int lim=2*sza;
    int act=0;
    long long ret=0;
    for(int i=0; i<lim; i++)
    {
        if(tmp[i].type==1)
        {
            if(act>=0)ret+=act;
            act++;
        }
        else act--;
    }
    //cout << ret << endl;
    return ret;
}
vector<Z>X,Y;

bool compx(Z A,Z B)
{
    if(A.a.st.y==B.a.st.y)return A.a.st.x<B.a.st.x;
    return A.a.st.y<B.a.st.y;
}

bool compy(Z A,Z B)
{
    if(A.a.st.x==B.a.st.x)return A.a.st.y<B.a.st.y;
    return A.a.st.x<B.a.st.x;
}

LLI solveX()
{
    if(X.size()==0)return 0;
    sort(X.begin(),X.end(),compx);
    LLI ret=0;
    sza=0;
    Arg[sza++]=X[0];
    for(int i=1; i<X.size(); i++)
    {
        if(X[i].a.st.y==X[i-1].a.st.y)
        {
            Arg[sza++]=X[i];
        }
        else
        {
            ret+=solve();
            sza=0;
            Arg[sza++]=X[i];
        }
    }
    if(sza>1)ret+=solve();
    return ret;
}
LLI solveY()
{
    if(Y.size()==0)return 0;
    sort(Y.begin(),Y.end(),compy);
    LLI ret=0;
    sza=0;
    Arg[sza++]=Y[0];
    for(int i=1; i<Y.size(); i++)
    {
        if(Y[i].a.st.x==Y[i-1].a.st.x)
        {
            Arg[sza++]=Y[i];
        }
        else
        {
            ret+=solve();
            sza=0;
            Arg[sza++]=Y[i];
        }
    }
    if(sza>1)ret+=solve();
    return ret;
}


int main()
{
    int kase,ks=0;
    scanf("%d",&kase);
    while(kase--)
    {
        V.clear();
        X.clear();
        Y.clear();
        int N;
        scanf("%d",&N);
        LLI x1,y1,x2,y2;
        REP(i,N)
        {
            scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
            if(x1>x2 || (x1==x2 && y1>y2))
            {
                swap(x1,x2);
                swap(y1,y2);
            }
            if(x2-x1==0)Y.PB(Line(Point(x1,y1),Point(x2,y2)));
            else if(y2-y1==0)X.PB(Line(Point(x1,y1),Point(x2,y2)));
            else V.PB(Line(Point(x1,y1),Point(x2,y2)));
        }
        long long res=0;
        long long ct=1;
        if(!V.empty())
        {
            SORT(V);
            sza=0;
            Arg[sza++]=V[0];

            for(int i=1; i<V.size(); i++)
            {
                if(same(V[i],V[i-1]))//slope
                {
                    if(CoLine(V[i],V[i-1]))
                    {
                        Arg[sza++]=V[i];
                    }
                    else
                    {
                        res+=(solve());
                        sza=0;
                        Arg[sza++]=V[i];
                    }
                }
                else
                {
                    res+=(solve());
                    sza=0;
                    Arg[sza++]=V[i];
                }
            }
            if(sza>1)res+=solve();
        }
        //cout << "......." << res << endl;
        res+=solveX();
        res+=solveY();
        printf("Case %d: %lld\n",++ks,res);
    }
    return 0;
}
/*
2
13
1 0 5 0
5 0 8 0
4 0 6 0
0 0 10 0

2 0 6 4
3 1 6 4
4 2 7 5

-6 0 0 -6
-5 -1 -7 1
-1 -5 1 -7

2 1 2 3
2 2 2 -4
2 -1 2 10
*/