Pagini recente » Cod sursa (job #76751) | Cod sursa (job #2783053) | Cod sursa (job #1188429) | Cod sursa (job #1723052) | Cod sursa (job #565617)
Cod sursa(job #565617)
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define nmax 100015
#define x first
#define y second
#define inf 1LL<<62
#define eps 0.0000000001
using namespace std;
typedef pair <int, int> ii;
int n;
ii p [nmax], f [nmax], v [nmax];
void scan ()
{
int i;
scanf ("%d", &n);
for (i=1; i <= n; ++i) scanf ("%d%d", &p [i].x, &p [i].y);
sort (p+1, p+1+n);
for (i=1; i <= n; ++i) v [i]=p [i];
}
inline long long min (long long a, long long b)
{
if (a < b)
return a;
return b;
}
inline long long dist (ii p1, ii p2)
{
return 1LL*(p1.x-p2.x)*(p1.x-p2.x)+1LL*(p1.y-p2.y)*(p1.y-p2.y);
}
inline void merge (int st, int dr)
{
int m=(st+dr)/2, i1=st, i2=m+1, num=0;
while (i1 <= m && i2 <= dr)
{
if (p [i1].y <= p [i2].y)
f [++num]=p [i1++];
else
f [++num]=p [i2++];
}
for (; i1 <= m; ++i1) f [++num]=p [i1];
for (; i2 <= dr; ++i2) f [++num]=p [i2];
for (i1=1; i1 <= num; ++i1)
p [st+i1-1]=f [i1];
}
long long cmap (int st, int dr)
{
if (st == dr)
return inf;
if (st+1 == dr)
{
if (p [st].y > p [dr].y)
{
ii aux=p [st];
p [st]=p [dr];
p [dr]=aux;
}
return dist (p [st], p [dr]);
}
int m=(st+dr)/2, i, j, num=0;
long long s=min (cmap (st, m), cmap (m+1, dr));
merge (st, dr);
// for (i=st; i <= dr; ++i) fprintf (stderr, "(%d %d) ", p [i].x, p [i].y);
// fprintf (stderr, "\n\n\n");
for (i=st; i <= dr; ++i)
if (p [i].x >= v [m].x-s && p [i].x <= v [m].x+s)
f [++num]=p [i];
for (i=1; i <= num; ++i)
for (j=1; j <= 7; ++j)
{
if (i+j > num) continue;
s=min (s, dist (p [i], p [i+j]));
}
return s;
}
int main ()
{
freopen ("cmap.in", "r", stdin);
freopen ("cmap.out", "w", stdout);
scan ();
printf ("%lf\n", sqrt (cmap (1, n)));
return 0;
}