Pagini recente » Cod sursa (job #927974) | Cod sursa (job #2215312) | Cod sursa (job #1258612) | Cod sursa (job #326767) | Cod sursa (job #1374105)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <limits>
#include <cmath>
using namespace std;
struct point {
int x;
int y;
point(int _x, int _y)
: x(_x)
, y(_y)
{}
};
struct comp_x {
bool operator() (const point& lp, const point& rp)
{
return (lp.x == rp.x)
? lp.y < rp.y
: lp.x < rp.x;
}
};
double euclid_dist(const point& lp, const point& rp)
{
return sqrt(1LL * (lp.x - rp.x) * (lp.x - rp.x) +
1LL * (lp.y - rp.y) * (lp.y - rp.y));
}
double min_dist_impl(const vector<point>& points_x,
int left,
int right)
{
if (left == right)
return numeric_limits<double>::max();
if (left + 1 == right) /* two points left in the set */
return euclid_dist(points_x[left], points_x[right]);
int middle = left + (right - left) / 2;
auto delta = min(
min_dist_impl(points_x, left, middle), /* left side */
min_dist_impl(points_x, middle + 1, right) /* right side */
);
vector<point> points_y;
for (int i = left; i <= right; i++) {
if (abs(points_x[i].x - points_x[middle].x) < delta) {
points_y.push_back(points_x[i]);
}
}
/* compute crossing min distance */
for (auto i = 0; i < static_cast<int>(points_y.size()) - 1; i++) {
for (auto j = i + 1; j < static_cast<int>(points_y.size()) &&
j - i < 7;
j++) {
auto dst = euclid_dist(points_y[i], points_y[j]);
if (dst > 0 && dst < delta) {
delta = dst;
}
}
}
return delta;
}
double min_dist(const vector<point>& points_x)
{
return min_dist_impl(points_x, 0, points_x.size() - 1);
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int N;
fin >> N;
vector<point> points_x; /* points sorted by x coordinate */
for (int i = 1; i <= N; i++) {
int x, y;
fin >> x >> y;
points_x.emplace_back(x, y);
}
sort(points_x.begin(), points_x.end(), comp_x{});
fout << setprecision(6) << fixed << min_dist(points_x);
return 0;
}