Pagini recente » Cod sursa (job #941744) | Cod sursa (job #941692) | Istoria paginii runda/simulare_oni_11-12./clasament | Istoria paginii runda/becreative11 | Cod sursa (job #941690)
Cod sursa(job #941690)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct point
{
int x, y;
};
bool compx(const point& a, const point& b)
{
return a.x < b.x;
}
bool compy(const point& a, const point& b)
{
return a.y < b.y;
}
double dist(const point& a, const point& b)
{
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
vector<point> p, q;
double d = 2e9;
point inf;
void findclosest(int l, int r)
{
vector<point> a;
if (r-l < 3) {
for (int i = l+1; i <= r; ++i)
for (int j = l; j < i; ++j)
d = min(d, dist(p[i],p[j]));
sort(q.begin()+l, q.begin()+r+1, compy);
return;
}
int m = (l+r)/2;
int median = p[m].x;
vector<point> b1, b2;
findclosest(l,m);
findclosest(m+1,r);
for (int i = l; i <= m; ++i)
if (median-q[i].x < d)
b1.push_back(q[i]);
for (int i = m+1; i <= r; ++i)
if (q[i].x-median < d)
b2.push_back(q[i]);
b1.push_back(inf);
b1.push_back(inf);
b2.push_back(inf);
b2.push_back(inf);
int i(0), j(0);
for (int k = b1.size()+b2.size()-4; k > 0; --k) {
d = min(d, dist(b1[i],b2[j]));
if (b1[i].y < b2[j].y)
d = min(d, dist(b1[i++],b2[j+1]));
else
d = min(d, dist(b1[i+1],b2[j++]));
}
inplace_merge(q.begin()+l, q.begin()+m+1, q.begin()+r+1,compy);
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
fin >> n;
p.resize(n);
for (int i = 0; i < n; ++i)
fin >> p[i].x >> p[i].y;
sort(p.begin(), p.end(), compx);
q = p;
inf.y = 2e9;
findclosest(0, n-1);
fout.precision(6);
fout << fixed << d;
return 0;
}