Pagini recente » Istoria paginii runda/brasov_9_jr | Autentificare | Istoria paginii runda/juniori__1 | Istoria paginii runda/runda_de_codat_formule | Cod sursa (job #565599)
Cod sursa(job #565599)
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define nmax 100015
#define x first
#define y second
#define eps 0.0000001
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 double min (double a, double b)
{
if (a < b)
return a;
return b;
}
inline double dist (ii p1, ii p2)
{
return sqrt ((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
inline double abs (double a)
{
if (a < 0) return -a;
return a;
}
bool cmp (ii a, ii b)
{
if (abs (a.y-b.y) <= eps)
{
if (a.x < b.x) return true;
return false;
}
return a.y < b.y;
}
double 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;
double s=min (cmap (st, m), cmap (m+1, dr));
for (i=st; i <= dr; ++i)
if (p [i].x >= p [m].x-s && 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", cmap (1, n));
return 0;
}