Pagini recente » Borderou de evaluare (job #1240715) | Borderou de evaluare (job #1409963) | Borderou de evaluare (job #2433900) | Borderou de evaluare (job #1536618) | Cod sursa (job #2244999)
#include <bits/stdc++.h>
#define N 100002
using namespace std;
struct point {
long long x, y;
} P[N];
vector<int> median_points;
long long dist2(point a, point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
long long find_min_dist(int a, int b) {
int i, j;
long long min_dist = LONG_LONG_MAX;
if (b - a + 1 <= 3) {
for (i = a; i <= b; i++)
for (j = i + 1; j <= b; j++)
min_dist = min(min_dist, dist2(P[i], P[j]));
} else {
// divide et impera
int m = (a + b) >> 1;
min_dist = min(find_min_dist(a, m), find_min_dist(m + 1, b));
median_points.clear();
for (i = a; i <= b; i++)
if (abs(P[i].x - P[m].x) <= min_dist)
median_points.push_back(i);
for (i = 0; i < median_points.size(); i++)
for (j = 1; j <= 7; j++)
if (i + j < median_points.size())
min_dist = min(min_dist, dist2(P[median_points[i]], P[median_points[i + j]]));
}
return min_dist;
}
int main() {
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
fin >> n;
for (int i = 1; i <= n; i++)
fin >> P[i].x >> P[i].y;
sort(P + 1, P + n + 1, [](const point &a, const point &b) -> bool { return a.x < b.x; });
fout << fixed << setprecision(6) << sqrt((double) find_min_dist(1, n));
return 0;
}