Pagini recente » Cod sursa (job #2573012) | Cod sursa (job #1976316) | Cod sursa (job #1643457) | Borderou de evaluare (job #1330706) | Cod sursa (job #3001300)
#include <bits/stdc++.h>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
struct punct {
long long x, y;
}v[100005], a[100005], aux[100005];
long long n;
long long distance(punct p1, punct p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
void merge(int l, int r, int m, punct v[]) {
int i = l, j = m + 1;
vector<punct> aux;
while (i <= m && j <= r) {
if (v[i].y <= v[j].y) aux.push_back(v[i++]);
else aux.push_back(v[j++]);
}
while (i <= m)
aux.push_back(v[i++]);
while (j <= r)
aux.push_back(v[j++]);
for (int i = 0; i < aux.size(); i++)
v[l + i] = aux[i];
}
double solve(long long l, long long r) {
if (r - l + 1 <= 3) {
sort(a + l, a + r + 1, [](const punct &p1, const punct &p2) {
return p1.y < p2.y;
});
long long dmin = distance(v[l], v[r]);
if (l + 1 != r) {
dmin = min(dmin, min(distance(v[l + 1], v[r]), distance(v[l], v[l + 1])));
}
return dmin;
}
long long m = (l + r) / 2;
long long dmin = min(solve(l, m), solve(m + 1, r));
merge(l, r, m, a);
int k = 0;
for (int i = l; i <= r; i++)
if (abs(a[i].x - v[m].x) <= dmin)
aux[++k] = a[i];
for (int i = 1; i <= k; i++) {
for (int j = i + 1; j <= k && j - i <= 8; j++)
dmin = min(dmin, distance(aux[i], aux[j]));
}
return dmin;
}
int main() {
in>>n;
for (int i = 1; i <= n; i++) {
in>>v[i].x>>v[i].y;
a[i] = v[i];
}
sort(v + 1, v + n + 1, [](const punct &p1, const punct &p2) {
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
});
out<<fixed<<setprecision(6)<<sqrt(solve(1, n))<<'\n';
}