Pagini recente » Cod sursa (job #994702) | Cod sursa (job #773880) | Istoria paginii runda/1234/clasament | Cod sursa (job #910709) | Cod sursa (job #1373435)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
#define INF ((1 << 30) * 1LL);
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) /* only one point left */
return INF;
if (left + 1 == right) /* two points left in the set */
return euclid_dist(points_x[left], points_x[right]);
auto 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 (auto i = left; i <= right; i++) {
if (max(
points_x[i].x - points_x[middle].x,
points_x[middle].x - points_x[i].x
) < delta) {
points_y.emplace_back(points_x[i]);
}
}
for (auto i = 0; i < points_y.size(); i++) {
for (auto j = i + 1; j < points_y.size() && j - i < 7; j++) {
if (euclid_dist(points_y[i], points_y[j]) > 0 &&
euclid_dist(points_y[i], points_y[j]) < delta) {
delta = euclid_dist(points_y[i], points_y[j]);
}
}
}
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 (auto 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;
}