Pagini recente » Cod sursa (job #1681291) | Cod sursa (job #1791154) | Cod sursa (job #1405071) | Cod sursa (job #2644765) | Cod sursa (job #1507574)
#include <fstream>
#include <limits.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fi("cmap.in");
ofstream fo("cmap.out");
#define MAX 100100
#define INF 2000000000
struct Point{
int x, y;
} p[MAX], y[MAX];
int n;
typedef long double ld;
ld dist(Point a, Point b)
{
return sqrt(1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y));
}
inline bool cmp(Point a, Point b)
{
return a.x < b.x;
}
ld closest(int st, int dr)
{
if(st == dr)
return INF;
if(st == dr - 1)
return dist(p[dr], p[st]);
int mij = (st + dr) / 2;
ld delta = min(closest(st, mij), closest(mij + 1, dr));
ld x = p[mij].x + p[mij + 1].x;
x /= 2;
int i = st;
int j = mij + 1;
int f = 0;
while(i <= mij && j <= dr)
{
if(p[i].x + delta < x)
i++;
else if(p[j].x - delta > x)
j++;
else
{
if(p[i].y < p[j].y)
{
y[++f] = p[i];
i++;
}
else
{
y[++f] = p[j];
j++;
}
}
}
while(i <= mij)
{
if(p[i].x + delta >= x)
y[++f] = p[i];
i++;
}
while(j <= dr)
{
if(p[j].x - delta <= x)
y[++f] = p[j];
j++;
}
for(i = 1 ; i <= f ; i++)
{
for(j = i + 1 ; j <= f ; j++)
{
if(y[j].y - delta > y[i].y)
break;
if(dist(y[i], y[j]) < delta)
delta = dist(y[i], y[j]);
}
}
return delta;
}
int main()
{
fi >> n;
for(int i = 1 ; i <= n ; i++)
{
fi >> p[i].x >> p[i].y;
}
sort(p + 1, p + n + 1, cmp);
fo << fixed << setprecision(6) << closest(1, n) << "\n";
fi.close();
fo.close();
return 0;
}