Pagini recente » Cod sursa (job #2057674) | Cod sursa (job #2799648) | Cod sursa (job #1461584) | Cod sursa (job #492316) | Cod sursa (job #1838176)
#include <cstdio>
#include <algorithm>
#define NMAX 100001
using namespace std;
FILE *f=fopen("cmap.in","r");
FILE *g=fopen("cmap.out","w");
typedef pair<long long,long long> point;
vector <point> V(NMAX);
vector<point> X,Y;
int N;
long long dist(point a,point b)
{
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
long long getmin(int st,int dr)///st...dr-1
{
if(st>=dr-1)
return (1LL<<62);
if(st==dr-2)
{
if(Y[dr-1]<Y[st])
swap(Y[st],Y[dr-1]);
return dist(Y[st],Y[dr-1]);
}
int mid=(st+dr)/2;
long long minim=min(getmin(st,mid),getmin(mid,dr));
merge(Y.begin()+st,Y.begin()+mid,Y.begin()+mid,Y.begin()+dr,V.begin());
copy(V.begin(),V.begin()+(dr-st),Y.begin()+st);
int ind=0;
for(int i=st;i<dr;i++)
if(abs(Y[i].second-X[i].first)<=minim)
V[ind++]=Y[i];
for(int i=0;i<ind;i++)
for(int j=i+1;j<ind&&j-i<=7;j++)
minim=min(minim,dist(V[j],V[i]));
return minim;
}
int main()
{
fscanf(f,"%d",&N);
X.resize(N);
Y.resize(N);
for(int i=0;i<N;i++)
fscanf(f,"%d%d",&X[i].first,&X[i].second);
for(int i=0;i<N;i++)
Y[i]=make_pair(X[i].second,X[i].first);
fprintf(g,"%.6f",sqrt(double(getmin(0,N))));
fclose(f);
fclose(g);
return 0;
}