Cod sursa(job #717364)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 19 martie 2012 21:13:54
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define INF 999999999999999999
#define type long long
#define PI pair<type,type>
#define MP make_pair
#define PB push_back
#define x first
#define y second
#define SZ size()
#define BG begin()
#define ED end()
#define NMAX 100010

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

vector<PI> V(NMAX),X,Y;
type n,i,ra,rb;

type Dist(PI a,PI b) {return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

type MinDist(int left,int right,vector<PI> &X,vector<PI> &Y) {
    if (left+1>=right) return INF;
    if (right-left==2) {
        if (Y[left]>Y[left+1]) swap(Y[left],Y[left+1]);
        return Dist(X[left],X[left+1]);
    }
    int middle=left+(right-left)/2;
    type ANS=min(MinDist(left,middle,X,Y),MinDist(middle,right,X,Y));
    merge(Y.BG+left,Y.BG+middle,Y.BG+middle,Y.BG+right,V.BG);
    copy(V.BG,V.BG+(right-left),Y.BG+left);
    V.clear();
    for (int i=left;i<right;i++)
        if (abs(Y[i].y-X[middle].x)<=ANS)
            V.PB(Y[i]);
    for (int i=0;i<V.SZ;i++)
        for (int j=i+1;j<V.SZ && j<i+8;j++)
            ANS=min(ANS,Dist(V[i],V[j]));
    return ANS;
}

int main() {
    f >> n;
    for (i=0;i<n;i++) {
        f >> ra >> rb;
        X.PB(MP(ra,rb));
        Y.PB(MP(rb,ra));
    }
    sort(X.begin(),X.end());
    g << fixed << setprecision(8) << sqrt((double)MinDist(0,n,X,Y)) << '\n';
    f.close();g.close();
    return 0;
}