Pagini recente » Cod sursa (job #849505) | Cod sursa (job #2902245) | Cod sursa (job #2299988) | Cod sursa (job #3206133) | Cod sursa (job #3239813)
///pentru simplitate poti lua toate punctele la distanta <= d, necontand partea si sa verifici primele 8 in sus sau ceva
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <vector>
#define double long double
using namespace std;
ifstream cin ("cmap.in");
ofstream cout ("cmap.out");
const double MAX = (double)(4e18);
const int N = 1e5;
struct point
{
int x, y;
} a[N + 1];
int n, bulan = 8;
double dist (point a, point b)
{
return sqrt(((double)(a.x - b.x) * (double)(a.x - b.x) + (double)(a.y - b.y) * (double)(a.y - b.y)));
}
inline double ab (double x)
{
if (x < 0)return -x;
return x;
}
bool cmp (const point &a, const point &b)
{
return a.y < b.y;
}
double divide (int l, int r)
{
if (l == r)
return MAX;
int mid = (l + r) >> 1;
double left_ans = divide (l, mid);
double right_ans = divide (mid + 1, r);
double d = min (left_ans, right_ans);
double center = (double)a[mid].x;
for (int i = l; i <= mid; ++i)
center = max (center, (double)a[i].x);
sort (a + l, a + r + 1, cmp);
vector <point> p;
for (int i = l; i <= r; ++i)
if (ab (center - a[i].x) <= d)
p.push_back(a[i]);
for (int i = 0; i < p.size(); ++i)
for (int j = i + 1; j < min (i + bulan, (int)(p.size())); ++j)
{
if (d > dist (p[i], p[j]))
d = dist (p[i], p[j]);
}
return d;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i].x >> a[i].y;
sort (a + 1, a + n + 1, [](const point &a, const point &b)
{
return a.x < b.x;
});
cout << fixed << setprecision(6) << divide (1, n) << '\n';
return 0;
}