Pagini recente » Cod sursa (job #2272538) | Cod sursa (job #2868320) | Cod sursa (job #1713896) | Cod sursa (job #2697175) | Cod sursa (job #703775)
Cod sursa(job #703775)
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define I64 long long
#define maxN 100005
#define INF 1LL << 61
using namespace std;
FILE*f=fopen("cmap.in","r");
FILE*g=fopen("cmap.out","w");
int n,i; double Dmin;
struct pct{
int x;
int y;
}a[maxN],b[maxN],vaux[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 I64 dist( pct a, pct b ){
I64 aux = 1LL*(a.x - b.x) * (a.x - b.x) + 1LL*(a.y - b.y) * (a.y - b.y);
return aux;
}
inline I64 abs( I64 j ){
if ( j < 0 )
return -j;
return j;
}
inline void swap( int u , int v ){
pct aux = a[u];
a[u] = a[v];
a[v] = aux;
}
inline I64 Min ( I64 a , I64 b ){
if ( a < b )
return a;
return b;
}
inline void read () {
fscanf(f,"%d",&n);
for ( i = 1 ; i <= n ; ++i ){
fscanf(f,"%d %d",&a[i].x,&a[i].y);
}
sort(a+1,a+n+1,cmp());
for ( i = 1; i <= n ; ++i ) b[i] = a[i];
}
inline void merge ( int st, int dr , int mj ){
int i,i1,i2,nr = 0;
for ( i1 = st , i2 = mj + 1 ; i1 <= mj && i2 <= dr ; ){
if ( a[i1].y < a[i2].y ){
vaux[++nr] = a[i1++];
}
else{
vaux[++nr] = a[i2++];
}
}
for ( ; i1 <= mj ; ++i1 )
vaux[++nr] = a[i1];
for ( ; i2 <= dr ; ++i2 )
vaux[++nr] = a[i2];
for ( i = st , nr = 0 ; i <= dr ; ++i ){
a[i] = vaux[++nr];
}
}
I64 Div( int st , int dr ){
if ( st >= dr ) return INF;
I64 S;
if ( !(dr - st -1) ){
if ( a[st].y > a[dr].y ){
swap(st,dr);
}
S = dist(a[st],a[dr]);
return S;
}
int mj = ( st + dr ) >> 1;
S = Min(Div(st,mj) , Div(mj+1,dr));
merge(st,dr,mj);
int i , j , nr = 0;
for ( i = st ; i <= dr ; ++i ){
if ( abs( a[i].x - b[mj].x ) ){
vaux[++nr] = a[i];
}
}
for ( i = 1 ; i <= nr ; ++i ){
for ( j = 1 ; j <= 7 ; ++j ){
if ( i + j <= nr ){
S = Min(S,dist(vaux[i],vaux[i+j]));
}
}
}
return S;
}
int main () {
read();
Dmin = sqrt(Div(1,n));
fprintf(g,"%lf\n",Dmin);
fclose(f);
fclose(g);
return 0;
}