1901.txt

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

#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

const int size = 1000;

struct point
{
	double x, y, z;
	int k;
}p[size];

inline double dis( point &a, point &b )
{
	return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + (a.z-b.z)*(a.z-b.z);
}

double dist[size][size];
typedef pair< double, int > type;
type s[size*size];
int n, m;

void init( )
{
	int i, j;
	scanf( "%d", &n );
	
	for( i=0; i<n; i++ )
		scanf( "%lf %lf %lf %d", &p[i].x, &p[i].y, &p[i].z, &p[i].k );

	m = 0;
	for( i=0; i<n; i++ )
	for( j=i+1; j<n; j++ )
	{
		s[m].first = dis( p[i], p[j] );
		s[m].second = i*n+j;
		m++;
	}

	sort( s, s+m );
}

int N[size];

void doit( )
{
	int ans = 0, j, i, t, a, b;
	double len = 0;

	for( i=0; i<n; i++ )
		N[i] = 1;

	t = 0;
	s[m].first = 1e100;
	for( i=0; i<m; i=j )
	{
		for( j=i; s[j].first < s[i].first + 1e-6 ; j++ )
		{
			a = s[j].second / n;
			b = s[j].second % n;
			if( p[a].k == p[b].k )
			{
				N[a]++, N[b]++;
				if( N[a] == 0 )
					t--;
				if( N[b] == 0 )
					t--;
			}
			else
			{
				N[a]--, N[b]--;
				if( N[a] == -1 )
					t++;
				if( N[b] == -1 )
					t++;
			}
		}

		if( t > ans )
		{
			ans = t;
			len = s[i].first;
		}
	}

	printf( "%d\n%.4lf\n", ans, sqrt(len) );
}

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