Pagini recente » Cod sursa (job #782401) | Cod sursa (job #1012777) | Cod sursa (job #1846358) | Cod sursa (job #373998) | Cod sursa (job #579426)
Cod sursa(job #579426)
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
#define DIM 100005
#define OO ((1LL<<61)-1)
#define minim(a,b) (a<b?a:b)
ifstream fi("cmap.in");
ofstream fo("cmap.out");
int N;
struct pct { int x, y; } P[DIM], M[DIM];
struct cmp
{
inline bool operator() (const pct &a, const 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;
pct V = P[m];
long long s = minim(die(st, m), die(m+1, dr)), d;
merge(st, m, dr);
int i, j, k = 0;
for (i = st; i <= dr; i++)
//if (pit(V, P[i]) <= s)
if (abs (V.x - P[i].x) <= 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;
}
void afs()
{
double d = sqrt((double)die(1, N));
/*
d *= 10000000;
if ((int)d % 10 >= 5) d += 10;
d /= 10000000;
*/
fo << setprecision(25) << d;
}
int main()
{
cit();
afs();
return 0;
}