Pagini recente » Cod sursa (job #2862404) | Cod sursa (job #2231782) | Cod sursa (job #2395927) | Cod sursa (job #485442) | Cod sursa (job #565602)
Cod sursa(job #565602)
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define nmax 100015
#define x first
#define y second
#define eps 0.0000000001
using namespace std;
typedef pair <int, int> ii;
int n;
ii p [nmax], f [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);
}
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 ((long long)(p1.x-p2.x))*(p1.x-p2.x)+((long long)(p1.y-p2.y))*(p1.y-p2.y);
}
inline long long abs (long long a)
{
if (a < 0) return -a;
return a;
}
bool cmp (ii a, ii b)
{
if (a.y == b.y)
{
if (a.x < b.x) return true;
return false;
}
return a.y < b.y;
}
long long cmap (int st, int dr)
{
if (st+1 == dr)
return dist (p [st], p [dr]);
if (st+2 == dr)
return min (min (dist (p [st], p [st+1]), dist (p [st], p [st+2])), dist (p [st+1], p [st+2]));
int m=(st+dr)/2, i, j, num=0;
long long s=min (cmap (st, m), cmap (m+1, dr));
for (i=st; i <= dr; ++i)
if (abs (p [i].x-p [m].x) <= s)
f [++num]=p [i];
sort (f+1, f+1+num, cmp);
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;
}