Pagini recente » Cod sursa (job #1533709) | Cod sursa (job #1764779) | Cod sursa (job #3003087) | Cod sursa (job #2060448) | Cod sursa (job #897609)
Cod sursa(job #897609)
#include<stdio.h>
#include<algorithm>
#include<cmath>
#define maxn 100005
#define inf (1LL<<62)
using namespace std;
FILE*f=fopen("cmap.in","r");
FILE*g=fopen("cmap.out","w");
int n;
int B[maxn],v[maxn];
long long sol;
struct pct{
int x,y;
}A[maxn],aux[maxn];
struct cmp{
inline bool operator () ( const pct &a , const pct &b ){
if ( a.x != b.x )
return a.x < b.x;
return a.y < b.y;
}
};
inline long long dist ( const pct &a , const pct &b ){
return 1LL*(a.x-b.x)*(a.x-b.x) + 1LL*(a.y-b.y)*(a.y-b.y);
}
void solve ( int st , int dr ){
if ( dr-st <= 1 ){
return ;
}
int mij = (st+dr)>>1;
solve(st,mij);
solve(mij+1,dr);
int p = st,u = mij+1; v[0] = 0;
while ( p <= mij && u <= dr ){
if ( A[p].y <= A[u].y ){
v[++v[0]] = p++;
}
else{
v[++v[0]] = u++;
}
}
for ( ; p <= mij ; ++p ){
v[++v[0]] = p;
}
for ( ; u <= dr ; ++u ){
v[++v[0]] = u;
}
for ( int i = st ; i <= dr ; ++i ){
aux[i] = A[v[i-st+1]];
}
for ( int i = st ; i <= dr ; ++i ){
for ( int j = 1 ; j <= 7 && i+j <= dr ; ++j ){
sol = min(sol,dist(aux[i],aux[i+j]));
}
A[i] = aux[i];
}
}
int main () {
fscanf(f,"%d",&n);
for ( int i = 1 ; i <= n ; ++i ){
fscanf(f,"%d %d",&A[i].x,&A[i].y);
B[i] = A[i].x;
}
sort(A+1,A+n+1,cmp());
sort(B+1,B+n+1);
sol = inf;
solve(1,n);
fprintf(g,"%lf\n",sqrt(sol));
fclose(f);
fclose(g);
return 0;
}