Cod sursa(job #519190)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 4 ianuarie 2011 14:13:10
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<fstream>
#include<math.h>
#include<algorithm>
#include<iomanip>
#define inf "cmap.in"
#define outf "cmap.out"
#define NMax 101000
#define INF 100000000000000000LL
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

struct punct { long long x,y; };

punct P[NMax];
int N;

void read()
{
    punct p; long long x,y;
    f>>N;
    for(int i=1; i<=N; i++)
    {
        f>>x>>y; p.x=x; p.y=y;
        P[i] = p;
    }
}

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

inline long long p2(long long a) { return (a*a); }

inline long long dist(punct a, punct b) { return ( p2(a.x-b.x) + p2(a.y-b.y) );  }

long long dei(int st, int dr)
{
    if( dr-st <= 2 )
    {
        if( st == dr+1 ) return dist(P[st], P[dr]);
        long long r = INF;
        for(int i=st; i<st+2; i++)
            for(int j=i+1; j<=st+2; j++)
                if( dist(P[i], P[j]) < r ) r = dist(P[i], P[j]);
        return r;
    }

    int m, ls, ld;
    long long d1, d2, d;
    m = (st+dr)>>1;
    d1 = dei(st, m); d2 = dei(m+1, dr);
    d = min(d1, d2);

    for(int i=m; i>=st; i--)
        if( dist(P[m], P[i]) > d ) { ls = i+1; break; }

    for(int i=m+1; i<=dr; i++)
        if( dist(P[i], P[dr]) > d ) { ld = i-1; break; }

    for(int i=ls; i<=m; i++)
        for(int j=m+1; j<=ld; j++)
            if( dist(P[i], P[j]) < d ) d = dist(P[i], P[j]);
    return d;
}

struct cmp { bool operator () (const punct &a, const punct &b) { return (a.x<b.x); } };

void solve()
{
    sort( P+1, P+N+1, cmp() );
    g<< fixed << setprecision(6) << sqrt( dei(1,N) );
}

int main()
{
	read(); solve();
	f.close(); g.close();
	return 0;
}