3215.txt

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

Source

Problem Id:3215  User Id:fzk 
Memory:2388K  Time:732MS
Language:C++  Result:Accepted

Source 

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

int a[100000], b[100000];
int n;

struct action {
	double x;
	int l;
}p[100000];

bool cmp( const action &a, const action &b ) {
	return a.x < b.x;
}

int main()
{
	int i, m, l, j;
	double temp, x;
	bool key , solution;
	
	while( scanf( "%d", &n ) == 1 && n ) {
		
		key = false;
		solution = false;

		for( i=0; i<n; i++ ) {
			scanf( "%d%d", a+i, b+i );
			if( !a[i] && !b[i] )
				key = true;
		}

		if( n == 1 && key ) {
			printf( "(-inf,+inf)\n" );
			continue;
		}

		m = 0;
		for( i=0; i<n; i++ ) {
			if( b[i] != 0 ) {
				p[m].x = -1.0*a[i]/b[i];
				p[m].l = i;
				m++;
			}
		}

		sort( p, p+m, cmp );
		
		int up, mid, down;
		
		up = mid = down = 0;
		bool begined = false;

		for( i=0; i<n; i++ ) {
			temp = a[i] + b[i]*(p[0].x-1000);
			if( temp == 0 )
				mid ++;
			else if( temp > up )
				up++;
			else
				down++; 
		}

		if( key && up <= n/2 && up+mid > n/2 ) {
			begined = true;
			solution = true;
			printf( "(-inf," );
		}

		for( i=0; i<m; i=j ) {

			for( j=i; j<m && p[j].x-p[i].x<1e-10; j++ ) {
				l = p[j].l;
				if( a[l]+b[l]*(p[j].x-10) > 0 )
					up--, mid++;
				else
					down--, mid++;
			}

			if( !begined ) {
				if( up <= n/2 && up+mid > n/2 ) {
					x = p[i].x;
					if( x < 0 && x >= -0.005 )
						x = 0;
					printf( "[%.2lf,", x );
					while( solution )
						;
					solution = true;
					begined = true;
				}
			}
			
			for( j=i; j<m && p[j].x-p[i].x<1e-10; j++ ) {
				l = p[j].l;
				if( a[l]+b[l]*(p[j].x+10) > 0 )
					up++, mid--;
				else
					down++, mid--;
			}

			if( begined && !(up <= n/2 && up+mid > n/2) ) {
				begined = false;
				x = p[i].x;
				if( x < 0 && x >= -0.005 )
					x = 0;
				printf( "%.2lf]\n", x );
//				break;
			}
		}

		if( begined )
			printf( "+inf)\n" );
		if( !solution )
			printf( "-1\n" );
		
	}

	return 0;
}