Cod sursa(job #1008017)

Utilizator lucky1992Ion Ion lucky1992 Data 10 octombrie 2013 01:16:48
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 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";
}