Pagini recente » Cod sursa (job #1816328) | Cod sursa (job #1665987) | Cod sursa (job #1418348) | Cod sursa (job #1018815) | Cod sursa (job #569336)
Cod sursa(job #569336)
#include<fstream>
#include<vector>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#define NMAX 100001
#define INF 4e18
#define LL long long
using namespace std;
ifstream in("cmap.in");
FILE *out=fopen("cmap.out","wt");
int i,n;
vector< pair<LL,LL> > X,Y,V(NMAX);
long long a,b;
int v_size;
LL go(int st,int dr);
inline LL dist(pair<LL,LL> a, pair<LL,LL> b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
int main()
{
in>>n;
for(i=1;i<=n;i++)
{
in>>a>>b;
X.push_back(make_pair(a,b));
}
sort(X.begin(),X.end());
for(i=0;i<n;i++)
Y.push_back(make_pair(X[i].second,X[i].first));
fprintf(out,"%.06lf",sqrt(go(0,X.size())) );
return 0;
}
LL go(int st,int dr)
{
if(st>=dr-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;
LL best=min(go(st,mid),go(mid,dr));
for(i=st,v_size=0;i<dr;i++)
if(abs(Y[i].second-X[mid].first)<=best)
V[v_size++]=Y[i];
for(i=0;i<v_size-1;i++)
for(int j=i+1;j<v_size && j-i<8;j++)
best=min(best,dist(V[i],V[j]));
return best;
}