Poj Solution 2489

http://poj.org/problem?id=2489

#include <stdio.h>
#include <math.h>
#include <memory.h>
#include <algorithm>
using namespace std;


struct point
{
    int x,y;
};

struct line
{
    point a,b;
    int dx,dy;
}l[100001];

int n;
__int64 ans;


inline double crossproduct(point o, point a, point b)
{
    return (double)(a.x-o.x)*(b.y-o.y) - (double)(a.y-o.y)*(b.x-o.x);
}

void normal(line &l)
{
    if( l.a.x>l.b.x || ( (l.a.x==l.b.x) && l.a.y>l.b.y )  )
        swap( l.a, l.b );
}

void qiu( line &l)
{
    l.dx = l.b.x-l.a.x;
    l.dy = l.b.y-l.a.y;
}

///////////////////////////////////////////////////////////////

bool cmp1( line l1, line l2 )
{
    double temp = (double)l1.dx*l2.dy-(double)l2.dx*l1.dy;
    if( temp >  0 )
        return 1;

    if( temp == 0 && crossproduct( l1.a,l2.b,l2.a ) > 0 )
        return 1;
    
    return 0;
}

bool cmp_point( point a, point b )
{
    return a.x<b.x||( a.x==b.x && a.y<b.y );
}

bool cmp2( line l1, line l2 )
{
    if( l1.dx == 0 )
        return l1.a.y<l2.a.y||(l1.a.y==l2.a.y&&l1.b.y<l2.b.y);
    else
        return l1.a.x<l2.a.x||(l1.a.x==l2.a.x&&l1.b.x<l2.b.x);
}



//////////////////////////////////////////////////////////
inline int low_it(int a)
{
    return a&(a^(a-1));
}


int a[200010];
int m;

void set(int i)
{
    for(;i<=m;i+=low_it(i))
    {
        a[i]++;
    }
}

int count(int i)
{
    int ans=0;
    for(;i>0;i-=low_it(i))
    {
        ans+=a[i];
    }
    return ans;
}

/////////////////////////////////////////////////////////////////

int v[200100];

int find(int value )
{
    int a=1,b=m,c;
    
    while(a<=b)
    {
        c=(a+b)/2;
        if( v[c]-value == 0 )
            return c;
        else if(v[c]<value)a=c+1;
        else b=c-1;
    }

    while(1)
    {
        printf("asdf");
    }
    return -1;

}

void calc( int begin, int end )
{
    int i,k,temp,h;

//    for(i=begin;i<end;i++)
//        printf(":::%d  %d - %d %dn", l[i].a.x, l[i].a.y, l[i].b.x, l[i].b.y );
//    printf("n");

    for( i=begin; i<end; i++ )
    if( l[i].dx !=0  )
    {
        v[(i-begin)*2+1] = l[i].a.x;
        v[(i-begin)*2+2] = l[i].b.x;
    }
    else 
    {
        v[(i-begin)*2+1] = l[i].a.y;
        v[(i-begin)*2+2] = l[i].b.y;
    }

    sort( v+1, v+1+(end-begin)*2 );
    m = std::unique_copy( v+1, v+1+(end-begin)*2, v+1 ) - (v+1);


    memset( a,0,sizeof(int)*(m+5) );

//__int64 tm=ans;

    for( i=begin; i<end; i++ )
    {
        if( l[i].dx != 0 )
            k = find( l[i].a.x ), h = find( l[i].b.x ); 
        else k = find( l[i].a.y ), h = find( l[i].b.y );

        temp = i-begin-count(k);
        ans += temp;
        set(h);
    }
//printf(":%I64dn",ans-tm);
}

void init()
{
    int i;

    scanf("%d",&n);

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

        scanf( "%d %d %d %d", &l[i].a.x, &l[i].a.y, &l[i].b.x, &l[i].b.y );
        
        normal( l[i] );
        qiu( l[i] );

    }

}


void doit()
{
    ans = 0;
    
    int i,j;

    sort( l, l+n, cmp1 );

    for(j=0,i=1;i<n;i++)
    {
        while( i<n && (double)l[i].dx*l[i-1].dy-(double)l[i-1].dx*l[i].dy == 0 
            && crossproduct( l[i].a,l[i-1].b,l[i-1].a ) == 0 )
            i++;

        sort( l+j, l+i, cmp2 );
        
        if(i>j+1)
            calc( j, i );
        
        j=i;
    }

    printf( "%I64dn", ans );
}

int main()
{
    int cas,i=0;
//    freopen("sin","r",stdin);
    scanf( "%d", &cas );

    while( cas-- )
    {
        init();
        printf( "Scenario #%d:n", ++i );
        doit();
        printf("n");
    }

    return 0;
}