Cod sursa(job #1163743)

Utilizator cristitamasTamas Cristian cristitamas Data 1 aprilie 2014 16:44:48
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#define INF  ~(1LL<<63)
#define Nmax 100010
using namespace std;

pair <int, int> X[Nmax],Y[Nmax],aux[Nmax];

vector <pair <int, int> > Pct;

int N;

inline long long Distanta(pair<int,int> a,pair<int,int>b)
{
    return 1LL*(a.first-b.first)(a.first-b.first)+1LL*(a.second-b.second)*(a.second-b.second);
}

void Citire_si_formare()
{
    scanf("%d",&N);
    for(int i=0;i<N;++i)
        scanf("%d %d",&X[i].first,&X[i].second);
    sort(X,X+N);
    for(int i=0;i<N;++i)
    {
        Y[i].fist=X[i].second;
        Y[i].second=X[i].first;
    }
}

long long Divide(int st, int dr)
{
    if(dr-st<=1)
        return INF;
    if(dr-st==2)
    {
        if(Y[st]>Y[st+1])
            swap(Y[st],Y[st+1]);
        return Distanta(Y[st],Y[st+1])l
    }
    int mij=(st+dr)/2;
    long long minim=min(Divide(st,mij),Divide(mij,dr));
    merge(Y+st,Y+mid,Y+mid,Y+dr,aux);
    copy(aux,aux+dr-st,Y+st);
    for(int i=st;i<dr;++i)
    {
        if(abs(X[i].first-Y[i].second)<=minim)
            Pct.push_back(Y[i]);
    }
    for(int i=0;i<Pct.size();++i)
        for(int j=i+1;j< Pct.size() && j-i<=8 ; ++j)
            minim=min(minim,Distanta(Pct[i],Pct[j]));
    return minim;
}

int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    Citire_si_formare();
    long long d=Divide(0,N);
    double Rezultat= sqrt(d);
    printf("%llf",Rezultat);
    return 0;
}