Pagini recente » Cod sursa (job #855673) | Cod sursa (job #1073732) | Cod sursa (job #1404557) | Cod sursa (job #885136) | Cod sursa (job #1273549)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cassert>
struct Point
{
Point()
: Point(0, 0)
{
}
Point(const Point &other)
: Point(other.x, other.y)
{
}
Point(long long _x, long long _y)
: x(_x)
, y(_y)
{
}
Point &operator=(const Point &other)
{
x = other.x;
y = other.y;
return *this;
}
long long x;
long long y;
};
long long euclid_dist(const Point &lhs, const Point &rhs)
{
return (lhs.x - rhs.x) * (lhs.x - rhs.x) + (lhs.y - rhs.y) * (lhs.y - rhs.y);
}
long long brute_force_dist(const std::vector<Point> &V)
{
long long curr_min = std::numeric_limits<long long>::max();
for (auto i = 0; i < static_cast<int>(V.size() - 1); ++i)
for (auto j = i + 1; j < static_cast<int>(V.size()); ++j) {
long long curr_dist = euclid_dist(V[i], V[j]);
if (curr_dist < curr_min)
curr_min = curr_dist;
}
return curr_min;
}
long long min_crossing(const std::vector<Point> &Xl, const std::vector<Point> &Xd)
{
long curr_min = std::numeric_limits<long long>::max();
for (auto it = Xl.crbegin(); it != Xl.crend(); ++it) {
long long curr_dist = euclid_dist(Xd.front(), *it);
if (curr_dist < curr_min)
curr_min = curr_dist;
}
return curr_min;
}
long long min_dist(std::vector<Point> &X, std::vector<Point> &Y)
{
// Same size - mandatory
assert(X.size() == Y.size());
// Check end condition
if (X.size() <= 3)
return brute_force_dist(X);
int mid = X.size() / 2;
// Divide
std::vector<Point> Xl, Yl, Xd, Yd;
for (auto &point : X)
if (point.x < X[mid].x)
Xl.push_back(point);
else
Xd.push_back(point);
for (auto &point : Y)
if (point.x < X[mid].x)
Yl.push_back(point);
else
Yd.push_back(point);
// Conquer
return std::min(std::min(min_dist(Xl, Yl), min_dist(Xd, Yd)),
min_crossing(Xl, Xd));
}
struct XCompare : public std::binary_function<Point, Point, bool>
{
bool operator()(const Point &a, const Point &b)
{
return a.x < b.x;
}
};
struct YCompare : public std::binary_function<Point, Point, bool>
{
bool operator()(const Point &a, const Point &b)
{
return a.y < b.y;
}
};
int main()
{
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
int N;
fin >> N;
std::vector<Point> X_way(N);
for (auto i = 0; i < N; ++i)
fin >> X_way[i].x >> X_way[i].y;
std::vector<Point> Y_way = X_way;
std::sort(X_way.begin(), X_way.end(), XCompare());
std::sort(Y_way.begin(), Y_way.end(), YCompare());
fout << std::fixed << std::setprecision(6) << std::sqrt(min_dist(X_way, Y_way));
return 0;
}