Pagini recente » Cod sursa (job #11360) | Statistici ASEM-Lozovanu-Marina (rynalozovanu) | Cod sursa (job #2587557) | Cod sursa (job #2707751) | Cod sursa (job #2074072)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;
#define x first
#define y second
#define nMax 100000
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
pair<int, int> points[nMax], pointsY[nMax], aux[nMax];
long long d(pair<int, int> a, pair<int, int> b){
return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}
long long minDist(int l, int r){
if(r == l)
return INT_MAX;
else if(r - l == 1){
if(pointsY[r] < pointsY[l])
swap(pointsY[l], pointsY[r]);
return d(pointsY[l], pointsY[r]);
}
int mid = (l + r) >> 1;
long long minD = min( minDist(l, mid), minDist(mid + 1, r));
merge(pointsY + l, pointsY + mid + 1, pointsY + mid + 1, pointsY + r + 1, aux);
copy(aux, aux + (r - l + 1), pointsY + l);
int k = 0;
for(int i = l; i <= r; i++)
if(abs(points[mid].x - pointsY[i].y) <= minD && i != mid)
aux[k++] = pointsY[i];
for(int i = 0; i < k; i++)
for(int j = i + 1; j < k && j <= i + 8; j++)
minD = min(minD, d(aux[i], aux[j]));
return minD;
}
int main()
{
f >> n;
for(int i = 0; i < n; i++)
f >> points[i].x >> points[i].y;
sort(points, points + n);
for(int i = 0; i < n; i++)
pointsY[i] = make_pair(points[i].y, points[i].x);
g << fixed << setprecision(6) << sqrt(minDist(0, n - 1));
return 0;
}