Pagini recente » Cod sursa (job #1734262) | Cod sursa (job #673073) | Cod sursa (job #1051883) | Cod sursa (job #2779424) | Cod sursa (job #2530057)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct point {
double x, y;
};
#define inf 99999999
#define vd vector<point>
double get_dist(point a, point b) {
return sqrt((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;
}
double get_min_dist(point a, point b, point c) {
double d1 = get_dist(a, b);
double d2 = get_dist(b, c);
double d3 = get_dist(a, c);
double dm;
dm = d1 < d2 ? d1 : d2;
return d3 < dm ? d3 : dm;
}
vd interclasare(vd a, vd b) {
int n = a.size();
int m = b.size();
vd c(n + m);
int i = 0, j = 0;
int k = 0;
while (i < n && j < m) {
if (a[i].y < b[j].y) {
c[k] = a[i];
i++;
k++;
}
else {
c[k] = b[j];
j++;
k++;
}
}
while (i < n) {
c[k] = a[i];
i++;
k++;
}
while (j < m) {
c[k] = b[j];
j++;
k++;
}
return c;
}
double get_min_strip(vd strip) {
double min = inf;
int n = strip.size();
for (int i = 0; i <= n - 8; i++)
for (int j = i + 1; j < i + 8; j++) {
if (get_dist(strip[i], strip[j]) < min)
min = get_dist(strip[i], strip[j]);
}
return min;
}
double distantaMinima(int st, int dr, vd pointx, vd pointy) {
if (dr - st == 1) {
if (pointy[st].y > pointy[dr].y)
swap(pointy[st], pointy[dr]);
return get_dist(pointx[st], pointx[dr]);
}
if (dr - st == 2) {
sort(pointy.begin() + st, pointy.begin() + dr + 1, comparey);
return get_min_dist(pointx[st], pointx[st + 1], pointx[dr]);
}
else {
int mij = (st + dr) / 2;
point midPoint = pointx[mij];
double d1 = distantaMinima(st, mij, pointx, pointy);
double d2 = distantaMinima(mij, dr, pointx, pointy);
double dmin = d1 < d2 ? d1 : d2;
vd Pyl;
for (int i = st; i <= mij; i++)
Pyl.push_back(pointy[i]);
vd Pyr;
for (int i = mij + 1; i <= dr; i++)
Pyr.push_back(pointy[i]);
vd Pyres = interclasare(Pyl, Pyr);
vd strip;
for (int i = st; i < dr - st + 1; i++) {
if (abs(Pyres[i].x - midPoint.x) < dmin)
strip.push_back(Pyres[i]);
}
float minstrip = get_min_strip(strip);
return dmin < minstrip ? dmin : minstrip;
}
}
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);
/*for (auto x : pointx)
cout << x.x << " " << x.y << "\n";*/
//sort(pointy.begin(), pointy.end(), comparey);
g << std::setprecision(8) <<distantaMinima(0, n - 1, pointx, pointy);
return 0;
}