Pagini recente » Cod sursa (job #1464669) | Cod sursa (job #711909) | Cod sursa (job #1329073) | Cod sursa (job #2736802) | Cod sursa (job #2486361)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;
#define x first
#define y second
ifstream in("cmap.in");
ofstream out("cmap.out");
double dist_calc(int x1, int x2, int y1, int y2) {
double d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
return sqrt(d);
}
double div_et_imp(pair<int, int> v[], int n) {
double dist_min = dist_calc(v[0].x, v[1].x, v[0].y, v[1].y);
for (int i = 0; i < n; i ++) {
for (int j = i + 1; j < n; j ++) {
double dist = dist_calc(v[i].x, v[j].x, v[i].y, v[j].y);
if (dist < dist_min) dist_min = dist;
}
}
return dist_min;
}
int main() {
int n;
in >> n;
pair<int, int> p[n + 1];
double x_med = 0;
for (int i = 0; i < n; i ++) {
in >> p[i].x >> p[i].y;
x_med += p[i].x;
}
x_med /= n;
pair<int, int> a[n / 2 + 1], b[n / 2 + 1];
int pa = 0, pb = 0;
for (int i = 0; i < n; i ++) {
if (p[i].x < x_med) a[pa ++] = p[i];
else if (p[i].x > x_med) b[pb ++] = p[i];
}
double d = min(div_et_imp(a, pa), div_et_imp(b, pb));
vector <pair<int, int>> v;
for (int i = 0; i < n; i ++) {
if (abs(x_med - p[i].x) <= d) v.push_back({p[i].y, p[i].x});
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i ++) {
for (int j = i + 1; j < i + 8 && j < v.size(); j ++) {
d = min(d, dist_calc(v[i].y, v[j].y, v[i].x, v[j].x));
}
}
out << fixed << setprecision(6) << d;
return 0;
}