Cod sursa(job #975861)

Utilizator danalex97Dan H Alexandru danalex97 Data 21 iulie 2013 21:16:05
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;

ifstream F("cmap.in");
ofstream G("cmap.out");

#define x first
#define y second

typedef long long I64;
typedef pair<I64,I64> Pair;

const int Nmax = 100010;
const I64 oo = 1LL<<60;

Pair A[Nmax],B[Nmax];
int N;

bool cmpx( Pair a , Pair b )
{
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

bool cmpy( Pair a , Pair b )
{
    return a.y == b.y ? a.x < b.x : a.y < b.y;
}

I64 sqr(I64 a)
{
    return a*a;
}

I64 dist(Pair& a,Pair& b)
{
    return sqr(a.x-b.x) + sqr(a.y-b.y);
}

Pair V[Nmax];
int Sz = 0;

void merge(int st,int mid,int dr)
{
    int i=st,j=mid+1;
    Sz = 0;
    while ( i <= mid && j <= dr )
    {
        if ( cmpy(B[i],B[j]) )
        {
            V[++Sz] = B[i++];
            continue;
        }
        if ( cmpy(B[j],B[i]) )
        {
            V[++Sz] = B[j++];
            continue;
        }
        V[++Sz] = B[i++];
        V[++Sz] = B[j++];
    }
    while ( i <= mid ) V[++Sz] = B[i++];
    while ( j <= dr ) V[++Sz] = B[j++];
    for (int i=1,j=st;i<=Sz;++i,++j) B[j] = V[i];
}

I64 go(int st,int dr)
{
    if ( st >= dr )
        return oo;
    if ( dr - st == 1 )
    {
        if ( ! cmpy(B[st],B[dr]) )
            swap( B[st],B[dr] );
        return dist(A[st],A[dr]);
    }
    int mid = ( st + dr ) / 2;
    I64 out = min( go(st,mid),go(mid+1,dr) );

    merge(st,mid,dr);

    Sz = 0;
    for (int i=st;i<=dr;++i)
        if ( abs(B[i].x-A[mid].x) <= out )
            V[++Sz] = B[i];

    int ct = 8;
    for (int i=1;i<Sz;++i)
        for (int j=i+1;j<=Sz && j-i<ct;++j)
            out = min( out,dist(V[i],V[j]) );
    return out;
}

int main()
{
    F>>N;
    for (int i=1;i<=N;++i)
        F>>A[i].x>>A[i].y;

    sort(A+1,A+N+1,cmpx);
    for (int i=1;i<=N;++i)
        B[i] = A[i];

    G<<fixed<<setprecision(6)<<sqrt(go(1,N))<<"\n";
}