Pagini recente » Cod sursa (job #2816770) | Cod sursa (job #512104) | Cod sursa (job #1212439) | Monitorul de evaluare | Cod sursa (job #3345257)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long double ld;
const int N = 1e5 + 5;
int n;
pair<int, int> v[N];
ld distanta(pair<int, int> p1, pair<int, int> p2)
{
int dx, dy;
dx = p1.first - p2.first;
dy = p1.second - p2.second;
return hypot(dx, dy);
}
bool comp(pair<int, int> &p1, pair<int, int> &p2)
{
if (p1.second == p2.second)
return p1.first < p2.first;
return p1.second < p2.second;
}
ld divide(int st, int dr)
{
if (st == dr)
return 1e18;
if (st == dr - 1)
return distanta(v[st], v[dr]);
int m = (st + dr) / 2;
int x = v[m].first;
ld r1, r2, dmin;
r1 = divide(st, m);
r2 = divide(m + 1, dr);
dmin = min(r1, r2);
vector<pair<int, int>> a;
for (int i = st; i <= dr; i++)
if (abs(v[i].first - x) <= dmin)
a.push_back(v[i]);
sort(a.begin(), a.end(), comp);
for (int i = 0; i < a.size(); i++)
for (int j = i + 1; j < a.size() && abs(a[i].second - a[j].second) < dmin; j++)
{
dmin = min(dmin, distanta(a[i], a[j]));
}
return dmin;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].first >> v[i].second;
sort(v + 1, v + n + 1);
ld rasp = divide(1, n);
fout << fixed << rasp;
return 0;
}