# 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;
}

```
This entry was posted in poj. Bookmark the permalink.