2779.txt

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

Problem Id:2779  User Id:fzk 
Memory:2048K  Time:588MS
Language:G++  Result:Accepted

Source 

#include "stdio.h"
#include "math.h"
#include "algorithm"

struct point{
	int x, y;
	char c;
	int pos;
}p[510];

char word[510], w[510];

struct inter{
	double x;
	int p_index1, p_index2;
}r[250100];

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

int maxe( int a, int b ) {
	return a>b?a:b;
}

int mine( int a, int b ) {
	return a<b?a:b;
}

bool cmp2( inter a, inter b ) {
	int s1, s2;
	if( a.x != b.x )
		return a.x < b.x;
	s1 = mine( p[ a.p_index1 ].y, p[ a.p_index2 ].y );
	s2 = mine( p[ b.p_index1 ].y, p[ b.p_index2 ].y );
	
	if( s1 != s2 )
		return s1 < s2;

	return maxe( p[ a.p_index1 ].y, p[ a.p_index2 ].y ) <
			maxe( p[ b.p_index1 ].y, p[ b.p_index2 ].y );

}

int n, m;

void input( ) {
	int i, j;
	char c[2];
	scanf( "%d", &n );
	scanf( "%s", word );

	for( i=0; i<n; i++ ) {
		scanf( "%1s%d%d", &c[0], &p[i].x, &p[i].y );
		p[i].c = c[0];
	}

	for( i=0; i<n; i++ ){
		p[i].pos = 0;
		for( j=0; j<n; j++ )
			if( i!=j && cmp1( p[i], p[j] ) )
				p[i].pos++;
	}

	m = 0;
	for(i=0; i<n; i++ )
		for(j=i+1; j<n; j++ ) {
			if( p[i].y != p[j].y ) {
				r[m].x = p[i].x - double(p[j].x - p[i].x ) / ( p[j].y - p[i].y ) * p[i].y;
				if( fabs( r[m].x ) < 1e-8 )
					r[m].x = 0;
				r[m].p_index1 = i;
				r[m].p_index2 = j;
				m++;
			}
		}
	std::sort( r, r+m, cmp2 );
	for( i=0; i<n; i++ )
		w[ p[i].pos ] = p[i].c;
}

double s1[250100], s2[250100];

void doit( ) {
	int i, j, ok = 0, k1, k2, ans = 0;
	for( i=0; i<n; i++ )
		if( word[i] == w[i] )
			ok++;
	if( ok == n ) {
		s1[ans] = -1e300;
		s2[ans] = ( m>0 ? r[0].x : 1e300 );
		ans++;
	}
	for( i=0; i<m; i=j ) {
		for( j=i; j<m && fabs(r[j].x-r[i].x) < 1e-7; j++ ) {
			k1 = r[j].p_index1;
			k2 = r[j].p_index2;
			if( w[ p[k1].pos ] == word[ p[k1].pos ] )		
				ok--;
			if( w[ p[k2].pos ] == word[ p[k2].pos ] )
				ok--;
			if( w[ p[k1].pos ] == word[ p[k2].pos ] )
				ok++;
			if( w[ p[k2].pos ] == word[ p[k1].pos ] )
				ok++;

			std::swap( p[k1].pos, p[k2].pos );
			std::swap( w[p[k1].pos], w[p[k2].pos] );
		}
		if( ok == n ) {
			s1[ans] = r[i].x;
			if( j < m )
				s2[ans] = r[j].x;
			else
				s2[ans] = 1e300;
			ans++;
		}
	}
	printf( "%d\n", ans );
	for( i=0; i<ans; i++ ) {
		if( i )
			printf( " " );

		if( s1[i] < -1e200 )
			printf( "*" );
		else
			printf( "%.7lf", s1[i] );
		
		if( s2[i] > 1e200 )
			printf( " *" );
		else
			printf( " %.7lf", s2[i] );
	}
	printf( "\n" );

	return ;
}
int main( ) {
	input( );
	doit( );
	return 0;
}