Cod sursa(job #683060)

Utilizator vitaleamaldur vitalik vitalea Data 19 februarie 2012 21:51:51
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <fstream>
#include <cstdlib>
#define Inf 99999;

using namespace std;

class Pair
{

public :

    int x, y;

    Pair( int cX, int cY );
};

Pair :: Pair( int cX, int cY )
{
    x = cX;
    y = cY;
}

int compareX ( const void * a, const void * b)
{
    return ( ((Pair*)a)->x - ((Pair*)b)->x );
}

float min( float a, float b )
{
    return a < b ? a : b;
}

float distance( Pair v[], int i, int j )
{
    return sqrt( pow( ( v[ j ].x - v[ i ].x ), 2 ) + pow( ( v[ j ].y - v[ i ].y ), 2 ) );
}

int indexMax( Pair v[], int mid, int high, int d )
{
    int i;
    for( i = mid; i <= high; i++ )
    {
        if( abs( v[ i ].x - v[ mid ].x ) > d ) break;
    }
    return i - 1 ;
}

int indexMin( Pair v[], int mid, int low, int d )
{
    int i;
    for( i = mid; i >= low; i-- )
    {
        if( abs( v[ mid ].x - v[ i ].x ) > d ) break;
    }
    return i + 1 ;
}

float minDistance2D( Pair v[], int low, int high )
{
    qsort( v, high - low + 1, sizeof( Pair ), compareX );
    int mid = ( low + high ) / 2;
    if( low == high )
    {
        return Inf;
    }
    if( high - low == 1)
    {
        return distance( v, low, high );
    }
    float a = minDistance2D( v, low, mid );
    float b = minDistance2D( v, mid + 1, high );
    return min( a, b );
}
float function( Pair v[], int low, int high ){
    int mid = ( low + high ) / 2;
    float d = minDistance2D( v, low, high );
    int i = indexMin( v, mid, low, d );
    int j = indexMax( v, mid, high, d );
    for( int k = i; k <= j; k++ ){
        for( int l = i; l <= j; l++ ){
            if( k != l){
                d = min( d, distance( v, k, l) );
            }
        }
    }
    return d;
}

int main()
{
    int num;
    ifstream in ( "cmap.in" );
    ofstream out ( "cmap.out" );
    in >> num;
    Pair  * vector = ( Pair* ) malloc ( num * sizeof( Pair ) ) ;
    for( int i = 0; i < num; i++ ){
        int x;
        int y;
        in >> x;
        in >> y;
        vector[ i ] = Pair( x, y );
    }
    in.close();
    out << function( vector, 0 , num - 1 );
    out.close();
    return 0;
}