Cod sursa(job #1014757)

Utilizator ELHoriaHoria Cretescu ELHoria Data 23 octombrie 2013 11:04:22
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#define pii pair<int,int>
#define MP make_pair
#define x first
#define y second
#define i64 unsigned long long
 
using namespace std;
 
ifstream fin("cmap.in");
ofstream fout("cmap.out");
 
const int NMAX = int(1e5) + 2;
const i64 INF = 1ll<<61;
int N;
pii V[NMAX], X[NMAX], Y[NMAX];
 
inline i64 dist(const pii &a,const pii &b) {
    return  1ll*(a.x - b.x) * (a.x - b.x)  + 1ll*(a.y - b.y) * (a.y - b.y);
}
 
i64 solve(int st,int dr) {
    if(dr - st == 1) {
        return INF;
	}
    else 
	if(dr - st == 2) {
        if(Y[st] > Y[st + 1])
            swap(Y[st],Y[st + 1]);
        return dist(X[st],X[st + 1]);
    }
    int mid = (st + dr)/2 , K = 0;
    i64 bst = min(solve(st,mid),solve(mid,dr));
    merge(Y + st, Y + mid, Y + mid, Y + dr, V);
  
	for(int i = 0;i < dr - st;i++) {
		Y[st + i] = V[i];
	}
 
    for(int i = st;i < dr;++i) {
        if(1ll*(Y[i].y - X[mid].x)*(Y[i].y - X[mid].x) <= bst) { 
			V[K++] = Y[i];
		}
	}

    for(int i = 0;i < K;++i)
        for(int j = i + 1;j < K && j - i <8;++j)
            bst = min(bst,dist(V[i],V[j]));
    return bst;
}
 
int main()
{
    fin>>N;
    for(int i = 0;i < N;++i)
        fin>>X[i].x>>X[i].y;
 
    sort(X,X + N);

    for(int i = 0;i < N;++i)
        Y[i] = MP(X[i].y,X[i].x);
	
	double ret = sqrt(1.0*solve(0,N));
	fout.precision(10);
    fout<<fixed<<ret;
    return 0;
}