2489.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#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 %d\n", 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(":%I64d\n",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( "%I64d\n", 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;
}