# Poj Solution 1901

```http://poj.org/problem?id=1901

#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( "%dn%.4lfn", ans, sqrt(len) );
}

int main( )
{
init( );
doit( );

return 0;
}

```
This entry was posted in poj. Bookmark the permalink.