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;
}