Pagini recente » Cod sursa (job #2347190) | Cod sursa (job #3186689) | Cod sursa (job #2940700) | Cod sursa (job #2264575) | Cod sursa (job #780546)
Cod sursa(job #780546)
#include <cassert>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long int64;
struct puncte {
int x;
int y;
};
const int N = 100005;
const int INF = 0x3f3f3f3f;
int n;
puncte punct[N], mijloc[N];
int cmp(puncte a, puncte b)
{
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
int cmp2(puncte a, puncte b)
{
if (a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
double dist(puncte a, puncte b)
{
return sqrt((int64)(b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
double rezolva(int left, int right)
{
if (left == right)
return INF;
if (left == right - 1)
return dist(punct[left], punct[right]);
int mij = left + (right - left) / 2;
double sol_left = rezolva(left, mij);
double sol_right = rezolva(mij + 1, right);
double sol = min(sol_left, sol_right);
int dim = 0;
for (int i = left; i <= right; ++i)
if (punct[mij].x - sol <= punct[i].x && punct[i].x <= punct[mij].x + sol)
mijloc[++dim] = punct[i];
sort (mijloc + 1, mijloc + dim + 1, cmp2);
int n = 1;
for (int i = 1; i <= dim; ++i) {
while (n <= dim && mijloc[n].y <= mijloc[i].y + sol)
++n;
for (int j = i; j < n; ++j)
for (int k = j + 1; k <= n; ++k)
sol = min(sol, dist(mijloc[j], mijloc[k]));
i = n;
}
return sol;
}
int main()
{
assert(freopen("cmap.in", "r", stdin));
assert(freopen("cmap.out", "w", stdout));
assert(scanf("%d", &n) == 1);
for (int i = 1; i <= n; ++i)
assert(scanf("%d %d", &punct[i].x, &punct[i].y) == 2);
sort(punct + 1, punct + n + 1, cmp);
printf("%.12lf", rezolva(1, n));
}