Pagini recente » Cod sursa (job #829079) | Cod sursa (job #1801768) | Cod sursa (job #1829714) | Cod sursa (job #2029051) | Cod sursa (job #2053754)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MaxN 100000
#define oo 1LL<<62
#define ll long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> Point;
Point A[MaxN+1];
Point B[MaxN+1];
Point C[MaxN+1];
int N;
bool cmp(const Point A, const Point B)
{
if(A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
ll dist(Point A, Point B)
{
return 1LL * (A.x - B.x) * (A.x - B.x) + 1LL * (A.y - B.y) * (A.y - B.y);
}
ll Solve(int st, int dr)
{
if(st >= dr) return oo;
else if(dr - st == 1){
if(B[st] > B[dr]) swap(B[st], B[dr]);
return dist(A[st], A[dr]);
}
int i, j, k = 0, mid = (st + dr) / 2;
ll res;
res = min(Solve(st, mid), Solve(mid+1, dr));
merge(B + st, B + mid + 1, B + mid + 1, B + dr + 1, C, cmp);
for(i = st; i <= dr; ++i) B[i] = C[i-st];
for(i = st; i <= dr; ++i)
if((B[i].x - A[mid].x) * (B[i].x - A[mid].x) <= res) C[++k] = B[i];
for(i = 1; i < k; ++i)
for(j = i+1; j <= k && j - i <= 8; ++j)
res = min(res, dist(C[i], C[j]));
return res;
}
int main(){
FILE* fin = fopen("cmap.in","r");
FILE* fout = fopen("cmap.out","w");
int i;
fscanf(fin,"%d",&N);
for(i = 1; i <= N; ++i) fscanf(fin,"%d %d",&A[i].x,&A[i].y);
sort(A+1,A+N+1);
for(i = 1; i <= N; ++i) B[i] = A[i];
fprintf(fout,"%f\n",sqrt(Solve(1,N)));
return 0;
}