Pagini recente » Cod sursa (job #303867) | Cod sursa (job #2639657) | Cod sursa (job #294126) | Cod sursa (job #349415) | Cod sursa (job #1136138)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define Inf 4e18
using namespace std;
vector < pair<long long, long long > > X,Y,v(100005);
int N;
void citire() {
ifstream in("cmap.in");
int i;
in>>N;
X.resize(N);
Y.resize(N);
for(i=0;i<N;i++)
in>>X[i].first>>X[i].second;
sort(X.begin(),X.end());
for(i=0;i<N;i++)
Y[i]=make_pair(X[i].second,X[i].first);
in.close();
}
long long dist( pair <long long,long long> & A,pair <long long,long long> &B) {
return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}
long long divetimp(int st,int dr,vector <pair <long long,long long> > &X,vector <pair<long long,long long> > &Y) {
if(st>=dr-1)
return Inf;
else
if(dr-st==2) {
if(X[st].second>X[st+1].second)
swap(X[st],X[st+1]);
return dist(X[st],X[st+1]);
}
long long best;
int mij=(st+dr)/2;
pair<long long, long long > a=X[mij];
best=min(divetimp(st,mij,X,Y),divetimp(mij,dr,X,Y));
merge(X.begin() + st, X.begin() + mij, X.begin() + mij, X.begin() + dr, v.begin());
copy(v.begin(), v.begin() + (dr - st), v.begin() + st);
int nrelem=0;
for(int i=st;i<dr;++i)
if(abs(X[i].second-a.first)<=best)
v[nrelem++]=Y[i];
for(int i=0;i<nrelem-1;i++)
for(int j=i+1;j<nrelem &&(j-i)<8;++j)
best=min(best,dist(v[i],v[j]));
return best;
}
void solvenafis(){
ofstream out("cmap.out");
out<<fixed<<setprecision(6)<<sqrt((double)divetimp(0,N,X,Y))<<'\n';
out.close();
}
int main() {
citire();
solvenafis();
return 0;
}