Pagini recente » Cod sursa (job #582268) | Cod sursa (job #1599913) | Cod sursa (job #2248362) | Cod sursa (job #2696807) | Cod sursa (job #1865403)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <climits>
#define inf 0x3f3f3f3f
using namespace std;
struct Coord {
int x, y;
inline double dist(const Coord& a) {
return sqrt((double)((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)));
}
} v[100001];
int n;
inline bool cmp(const Coord& a, const Coord& b) {
return a.x < b.x;
}
int cautlb(int st, int dr, int val)
{
int mid;
while(st < dr)
{
mid = (st + dr) / 2;
if(v[mid].x <= val)
dr = mid;
else st = mid + 1;
}
mid = (st + dr) / 2;
if(v[mid].x < val)
mid++;
return mid;
}
int cautub(int st, int dr, int val)
{
int mid;
while(st < dr)
{
mid = (st + dr) / 2;
if(v[mid].x < val)
dr = mid;
else st = mid + 1;
}
mid = (st + dr) / 2;
if(v[mid].x > val)
mid--;
return mid;
}
double dmin(int st, int dr)
{
if(dr - st <= 2)
{
double rez = 99999999;
for(int i = st; i < dr; i++)
for(int j = i + 1; j <= dr; j++)
rez = min(rez, v[i].dist(v[j]));
return rez;
}
double m1 = dmin(st, (st + dr) / 2);
double m2 = dmin((st + dr) / 2 + 1, dr);
int delta = min(ceil(m1), ceil(m2));
int st1 = cautlb(st, (st + dr) / 2, v[(st + dr) / 2].x - delta);
int dr1 = cautub((st + dr) / 2 + 1, dr, v[(st + dr) / 2 + 1].x + delta);
double m3 = dmin(st1, dr1);
return min(m1, min(m2, m3));
}
int main()
{
int i;
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d%d", &v[i].x, &v[i].y);
}
sort(v, v + n, cmp);
double rez = dmin(0, n - 1);
printf("%f", rez);
return 0;
}