Pagini recente » Cod sursa (job #1329248) | Cod sursa (job #698028) | Cod sursa (job #547834) | Cod sursa (job #2395100) | Cod sursa (job #1689148)
#include <bits/stdc++.h>
using namespace std;
struct Point
{
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {};
double dist(const Point &other) const
{
double d1 = x - other.x, d2 = y - other.y;
return (d1 * d1 + d2 * d2);
}
};
const double INF = 1e15;
vector<Point>V;
int N;
void Read()
{
ifstream in("cmap.in");
in >> N; V.resize(N);
for(auto &act : V)
in >> act.x >> act.y;
sort(begin(V), end(V), [&] (const Point &a, const Point &b) { return a.x < b.x;});
}
double foo(int x , int y)
{
if(x == y) return 0;
if(y - x + 1 <= 3)
{
double ans = INF;
for(int i = x; i <= y; ++i)
for(int j = i + 1; j <= y; ++j) ans = min(ans, V[i].dist(V[j]));
return ans;
}
int mij = (x + y) / 2;
double better = min(foo(x, mij), foo(mij+1, y));
vector <Point>strip;
for(int k = x; k<= y; ++k)
if(fabs(V[k].x - V[mij].x) <= better)
strip.push_back(V[k]);
auto cmp = [&] (const Point &a, const Point &b) { return a.y < b.y;};
sort(begin(strip), end(strip), cmp);
for(int i = 0; i < (int)strip.size(); ++i)
for(int j = i + 1; j < (int)strip.size() && strip[i].dist(strip[j]) < better; ++j)
better = min(better, strip[i].dist(strip[j]));
return better;
}
int main()
{
Read();
ofstream("cmap.out")<<fixed<<setprecision(9)<<sqrt(foo(0, V.size() - 1));
return 0;
}