Pagini recente » Cod sursa (job #1073391) | Cod sursa (job #756780) | Cod sursa (job #2059142) | Cod sursa (job #294825) | Cod sursa (job #1273533)
#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(int _x, int _y)
: x(_x)
, y(_y)
{
}
Point &operator=(const Point &other)
{
x = other.x;
y = other.y;
return *this;
}
int x;
int y;
};
double euclid_dist(const Point &lhs, const Point &rhs)
{
return std::sqrt(std::pow(lhs.x - rhs.x, 2) + std::pow(lhs.y - rhs.y, 2));
}
double brute_force_dist(const std::vector<Point> &V)
{
double curr_min = std::numeric_limits<double>::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) {
double curr_dist = euclid_dist(V[i], V[j]);
if (curr_dist < curr_min)
curr_min = curr_dist;
}
return curr_min;
}
double min_crossing(const std::vector<Point> &Xl, const std::vector<Point> &Xd,
double pos_min)
{
std::vector<Point> X_sec;
for (auto it = Xl.crbegin(); it != Xl.crend(); ++it) {
if (euclid_dist(*it, Xd.front()) > pos_min)
break;
X_sec.push_back(*it);
}
return brute_force_dist(X_sec);
}
double 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
double pos_min = std::min(min_dist(Xl, Yl), min_dist(Xd, Yd));
return std::min(pos_min, min_crossing(Xl, Xd, pos_min));
}
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) << min_dist(X_way, Y_way);
return 0;
}