Pagini recente » Cod sursa (job #1459985) | Cod sursa (job #2740367) | Cod sursa (job #2227474) | Cod sursa (job #942525) | Cod sursa (job #2649797)
#include <bits/stdc++.h>
#define newline '\n'
#define STOP fout.close(); exit(EXIT_SUCCESS);
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
///******************************
#define x first
#define y second
typedef long long int64;
typedef pair<int64, int64> Point;
const int NMAX = 1e5 + 3;
int n, auxn;
Point p[NMAX], aux[NMAX];
void read() {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> p[i].x >> p[i].y;
}
void preCheck() {
for (int i = 1; i < n; i++)
if (p[i].x == p[i + 1].x && p[i].y == p[i + 1].y) {
fout << 0 << newline;
STOP
}
}
inline int64 to2(int64 x) {
return x * x;
}
inline int64 getDis(Point a, Point b) {
return 1LL * to2(a.x - b.x) + 1LL * to2(a.y - b.y);
}
void pmerge(int l, int r) {
int mid = (l + r) >> 1, i = l, j = mid + 1;
auxn = 0;
while (i <= mid && j <= r) {
if (p[i].y < p[j].y)
aux[++auxn] = p[i++];
else if (p[i].y > p[j].y)
aux[++auxn] = p[j++];
else {
if (p[i].x < p[j].x)
aux[++auxn] = p[i++];
else
aux[++auxn] = p[j++];
}
}
while (i <= mid)
aux[++auxn] = p[i++];
while (j <= r)
aux[++auxn] = p[j++];
for (j = 1, i = l; i <= r; i++, j++)
p[i] = aux[j];
}
int64 getMinDis(int l, int r) {
if (r - l + 1 == 3) {
pmerge(l + 1, r);
pmerge(l, r);
return min(getDis(p[l], p[l + 1]), min(getDis(p[l], p[r]), getDis(p[l + 1], p[r])));
}
else if (r - l + 1 == 2) {
pmerge(l, r);
return getDis(p[l], p[r]);
}
int mid = (l + r) >> 1;
int64 minDis = min(getMinDis(l, mid), getMinDis(mid + 1, r));
pmerge(l, r);
auxn = 0;
for (int i = l; i <= r; i++)
if (to2(p[mid].x - p[i].x) <= minDis)
aux[++auxn] = p[i];
for (int i = 1; i <= auxn; i++)
for (int j = i + 1; j - i + 1 <= 9 && j <= auxn; j++)
minDis = min(minDis, getDis(aux[i], aux[j]));
return minDis;
}
int main() {
read();
sort(p + 1, p + n + 1);
preCheck();
fout << setprecision(6) << fixed << sqrt(getMinDis(1, n));//*/
STOP
}