Pagini recente » Cod sursa (job #2103585) | Cod sursa (job #2774129) | Cod sursa (job #1147633) | Cod sursa (job #1900432) | Cod sursa (job #2530087)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct point {
long long x, y;
};
#define inf 99999999
#define vd vector<point>
long long get_dist_sqr(point a, point b) {
return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}
bool comparex(point a, point b) {
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
bool comparey(point a, point b) {
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
long long get_min_dist_sqr(point a, point b, point c) {
long long d1 = get_dist_sqr(a, b);
long long d2 = get_dist_sqr(b, c);
long long d3 = get_dist_sqr(a, c);
long long dm;
dm = d1 < d2 ? d1 : d2;
return d3 < dm ? d3 : dm;
}
long long get_min_strip(vd strip) {
long long min = inf;
int n = strip.size();
for (unsigned i = 0; i < n; i++)
for (unsigned j = i + 1; j < n and j < i + 8; j++) {
if (get_dist_sqr(strip[i], strip[j]) < min)
min = get_dist_sqr(strip[i], strip[j]);
}
return min;
}
long long distantaMinima(int st, int dr, vd &pointx, vd &pointy) {
/* if (dr - st == 1) {
return get_dist_sqr(pointx[st], pointx[dr]);
}
if (dr - st == 2) {
return get_min_dist_sqr(pointx[st], pointx[st + 1], pointx[dr]);
}*/
if (dr - st <= 3) {
long long dmin = get_dist_sqr(pointx[st], pointx[st + 1]);
for (unsigned i = st; i < dr; i++)
for (int j = i + 1; j <= dr; j++)
if (get_dist_sqr(pointx[i], pointx[j]) < dmin)
dmin = get_dist_sqr(pointx[i], pointx[j]);
return dmin;
}
else {
int mij = (st + dr) / 2;
point midPoint = pointx[mij];
vd ord_st, ord_dr;
for (unsigned i = 0; i < pointy.size(); i++) {
if (pointy[i].x <= midPoint.x)
ord_st.push_back(pointy[i]);
else
ord_dr.push_back(pointy[i]);
}
long long d1 = distantaMinima(st, mij, pointx, ord_st);
long long d2 = distantaMinima(mij + 1, dr, pointx, ord_dr);
long long dmin = d1 < d2 ? d1 : d2;
vd fasie;
for (unsigned i = 0; i < pointy.size(); i++) {
if (pointy[i].x > midPoint.x - sqrt(dmin) and
pointy[i].x < midPoint.x + sqrt(dmin))
fasie.push_back(pointy[i]);
/* if (abs(pointy[i].x - midPoint.x) < sqrt(dmin))
fasie.push_back(pointy[i]);*/
}
long long stripmin = get_min_strip(fasie);
return stripmin < dmin ? stripmin : dmin;
}
}
int main()
{
int n;
f >> n;
vd pointx(n), pointy(n);
for (int i = 0; i < n; i++) {
f >> pointx[i].x >> pointx[i].y;
pointy[i] = pointx[i];
}
sort(pointx.begin(), pointx.end(), comparex);
sort(pointy.begin(), pointy.end(), comparey);
g << std::setprecision(8) << sqrt(distantaMinima(0, n - 1, pointx, pointy));
return 0;
}