Pagini recente » Cod sursa (job #3180101) | Cod sursa (job #475491) | Cod sursa (job #2314681) | Cod sursa (job #871072) | Cod sursa (job #1000808)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair <int, int> point;
point v[100001];
int n, i;
double dist(point a, point b)
{
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
bool cmp(point a, point b)
{
return a.y < b.y;
}
double divide(int left, int right)
{
if(left >= right)
return 0x3f3f3f3f;
else if( left + 1 == right )
{
if (v[left].y > v[right].y)
swap(v[left], v[right]);
return dist(v[left], v[right]);
}
int mid = (left + right) >> 1;
double min_dist = min(divide(left, mid), divide(mid+1, right));
vector <point> strip;
for (int i = left; i <= right; ++i)
if( i!=mid && abs(v[mid].x - v[i].x) < min_dist)
strip.push_back(v[i]);
sort(strip.begin(), strip.end(), cmp);
for (int i = 0; i <strip.size(); ++i)
for(int j = i+1; j<=i+8 && j<strip.size(); ++j)
min_dist = min( min_dist, dist(strip[j], strip[i]) );
return min_dist;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%d", &n);
for(i=1; i<=n; ++i)
scanf("%d %d", &v[i].x, &v[i].y);
sort(v+1, v+n+1);
double nr=divide(1, n);
printf("%6lf\n",nr);
return 0;
}