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