Pagini recente » Cod sursa (job #2948946) | Cod sursa (job #527436) | Cod sursa (job #1920945) | Cod sursa (job #1649158) | Cod sursa (job #743863)
Cod sursa(job #743863)
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005;
const double inf = 3e10;
int n, sizeA, sizeB;
ifstream in("cmap.in");
ofstream out("cmap.out");
struct Punct
{
int x, y;
inline void get()
{
in >> x >> y;
}
inline bool operator< (const Punct& P) const
{
return x < P.x || ( x == P.x && y < P.y );
}
} v[N], stanga[N], dreapta[N];
inline bool cmp(const Punct& A, const Punct& B)
{
return A.y < B.y;
}
inline double min(double a, double b)
{
return a < b ? a : b;
}
inline double sq(double a)
{
return a * a;
}
inline double dist(Punct A, Punct B)
{
return sqrt(sq(A.x - B.x) + sq(A.y - B.y));
}
int bs(Punct v[], int n, double x)
{
int i, step = 1 << 16;
for (i = 1 ; step ; step >>= 1)
if (i + step <= n && v[i + step].y <= x)
i += step;
return i;
}
double join(Punct a[], Punct b[], double D)
{
int st, dr;
sort(b + 1, b + sizeB + 1, cmp);
for (int i = 1 ; i <= sizeA; i++)
{
st = bs(b, sizeB, a[i].y - D);
dr = bs(b, sizeB, a[i].y + D);
for (int j = st ; j <= dr ; j++)
D = min(D, dist(a[i], b[j]));
}
return D;
}
double cmap(int st, int dr)
{
if (dr <= st)
return inf;
int m = (st + dr) >> 1;
double D = min(cmap(st, m), cmap(m + 1, dr));
sizeA = sizeB = 0;
for (int i = st ; i <= m ; i++)
if (v[m].x - v[i].x < D)
stanga[++sizeA] = v[i];
for (int i = m + 1 ; i <= dr ; i++)
if (v[i].x - v[m].x < D)
dreapta[++sizeB] = v[i];
/*
double sht = join(stanga, dreapta, D);
cout << st << " " << dr << " " << sht << "\n";
return sht;
*/
if (!sizeA || !sizeB)
return D;
return join(stanga, dreapta, D);
}
int main()
{
int n;
in >> n;
for (int i = 1 ; i <= n ; i++)
v[i].get();
sort(v + 1, v + n + 1);
freopen("cmap.out", "w", stdout);
printf("%.6lf\n", cmap(1, n));
return 0;
}