Pagini recente » Cod sursa (job #1826600) | Cod sursa (job #1339520) | Cod sursa (job #1695519) | Cod sursa (job #2931557) | Cod sursa (job #1985708)
#include <bits/stdc++.h>
#define infl 0x7fffffffffffffffLL
using namespace std;
typedef long long llong;
struct Punct
{
int x, y;
} px[100005], py[100005], tmp[100005];
bool cmpx(const Punct& a, const Punct& b)
{
return a.x < b.x;
}
bool cmpy(const Punct& a, const Punct& b)
{
return a.y < b.y;
}
llong dist2(const Punct& a, const Punct& b)
{
llong dx = a.x - b.x;
llong dy = a.y - b.y;
return dx * dx + dy * dy;
}
llong calc(int p, int q)
{
llong res = infl;
for(int i = p; i < q; i++)
{
for(int j = i + 1; j <= q; j++)
{
llong aux = dist2(px[i], px[j]);
if(aux < res)
res = aux;
}
}
return res;
}
llong solve(int p, int q)
{
if(q - p < 3)
return calc(p, q);
int m = (p + q) / 2;
llong d1 = solve(p, m);
llong d2 = solve(m + 1, q);
llong dd = min(d1, d2);
sort(py + p, py + q + 1, cmpy);
int k = 0;
for(int i = p; i <= q; i++)
{
llong dist = py[i].x - px[m].x;
if(dist * dist < dd)
tmp[k++] = py[i];
}
for(int i = 0; i < k; i++)
{
for(int j = i + 1; j < i + 8 && j < k; j++)
{
llong dist = dist2(tmp[i], tmp[j]);
if(dd > dist)
dd = dist;
}
}
return dd;
}
int main()
{
int n, i;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
fin >> n;
for(i = 0; i < n; i++)
{
fin >> px[i].x >> px[i].y;
py[i] = px[i];
}
sort(px, px + n, cmpx);
llong res = solve(0, n - 1);
fout << fixed << setprecision(6) << sqrtl(res);
return 0;
}