Pagini recente » Cod sursa (job #1645571) | Cod sursa (job #2094802) | Cod sursa (job #1577821) | Cod sursa (job #2108542) | Cod sursa (job #2530068)
#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 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;
}
long double get_min_strip(vd strip) {
long double min = inf;
int n = strip.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n and 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) {
return get_dist(pointx[st], pointx[dr]);
}
if (dr - st == 2) {
return get_min_dist(pointx[st], pointx[st + 1], pointx[dr]);
}
else {
int mij = (st + dr) / 2;
point midPoint = pointx[mij];
vd ord_st, ord_dr;
for (int 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 double d1 = distantaMinima(st, mij, pointx, ord_st);
long double d2 = distantaMinima(mij, dr, pointx, ord_dr);
long double dmin = d1 < d2 ? d1 : d2;
vd fasie;
for (int i = 0; i < pointy.size(); i++) {
if (abs(pointy[i].x - midPoint.x) < dmin)
fasie.push_back(pointy[i]);
}
long double 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) <<distantaMinima(0, n - 1, pointx, pointy);
return 0;
}