Pagini recente » Cod sursa (job #326772) | Cod sursa (job #483811) | Cod sursa (job #613408) | Cod sursa (job #2240965) | Cod sursa (job #864721)
Cod sursa(job #864721)
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
#include <utility>
using namespace std;
#define x first
#define y second
#define MAXN 100005
#define INF 1e17
typedef pair<int, int> Point;
int N;
Point P[MAXN], Y[MAXN], AUX[MAXN];
inline long long dist(const Point &a, const Point &b) {
return (long long)(a.x - b.x) * (a.x - b.x) + (long long)(a.y - b.y) * (a.y - b.y);
}
long long minDist(int st, int dr) {
if(dr - st + 1 <= 3) {
long long ret = INF;
for(int i = st; i < dr; i++)
for(int j = i + 1; j <= dr; j++) {
ret = min(ret, dist(P[i], P[j]));
if(Y[i].y > Y[j].y)
swap(Y[i], Y[j]);
}
return ret;
}
int m = (st + dr) / 2;
long long ret1 = minDist(st, m);
long long ret2 = minDist(m + 1, dr);
long long ret = min(ret1, ret2);
/*
int i, j, k;
i = st;
while(i <= m) {
AUX[i] = Y[i];
i++;
}
j = k = st;
while(i <= dr && j < i) {
if(Y[i].y < AUX[j].y)
Y[k++] = Y[i++];
else
Y[k++] = AUX[j++];
}
while(j < i)
Y[k++] = AUX[j++];
while(i <= dr)
Y[k++] = Y[i++];
*/
merge(Y + st, Y + m + 1, Y + m + 1, Y + dr + 1, Y + st);
for(int i = st; i <= dr; i++)
for(int j = i + 1; j <= i + 7 && j <= dr; j++)
ret = min(ret, dist(Y[i], Y[j]));
return ret;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out","w", stdout);
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d %d", &P[i].x, &P[i].y);
sort(P, P + N);
for(int i = 0; i < N; i++)
Y[i] = P[i];
vector<int> v;
double ans = sqrt(minDist(0, N - 1));
printf("%.6lf\n", ans);
return 0;
}