Pagini recente » Cod sursa (job #2553193) | Cod sursa (job #1062686) | Cod sursa (job #1969715) | Cod sursa (job #1901710) | Cod sursa (job #579391)
Cod sursa(job #579391)
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
#define DIM 100005
#define OO (1<<31) - 1
ifstream fi("cmap.in");
ofstream fo("cmap.out");
int N;
struct pct { int x, y; } P[DIM], M[DIM];
int cmp(pct a, pct b)
{
return a.x < b.x;
}
long long pit(pct a, pct b)
{
long long x = a.x - b.x;
long long y = a.y - b.y;
return x*x + y*y;
}
void merge(int st, int m, int dr)
{
int i = st, j = m+1, k = 0;
while (i <= m && j <= dr)
if (P[i].y < P[j].y)
M[++k] = P[i++];
else
M[++k] = P[j++];
while (i <= m)
M[++k] = P[i++];
while (j <= dr)
M[++k] = P[j++];
for (i = st; i <= dr; i++)
P[i] = M[i-st+1];
}
void cit()
{
fi >> N;
for (int i = 1; i <= N; i++)
fi >> P[i].x >> P[i].y;
sort(P + 1, P + N + 1, cmp);
}
long long die(int st, int dr)
{
if (st >= dr)
return OO;
if (st + 1 == dr)
{
if (P[st].y > P[dr].y)
{
pct aux = P[st];
P[st] = P[dr];
P[dr] = aux;
}
return pit(P[st], P[dr]);
}
int m = st + dr >> 1;
long long s = min(die(st, m), die(m+1, dr)), d;
pct V = P[m];
merge(st, m, dr);
int i, j, k = 0;
for (i = st; i <= dr; i++)
if (pit(V, P[i]) <= s)
M[++k] = P[i];
for (i = 1; i <= k; i++)
for (j = i + 1; j <= i + 7 && j <= k; j++)
{
d = pit(M[i], M[j]);
s = s < d ? s : d;
}
return s;
}
int main()
{
cit();
fo << setprecision(8) << sqrt((double)die(1, N));
return 0;
}