Pagini recente » Monitorul de evaluare | Istoria paginii runda/pre0001 | Istoria paginii runda/bravo5 | Atasamentele paginii runda_ezoterica_1 | Cod sursa (job #2076207)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#define nMax 1000
using namespace std;
struct point {
float x, y;
}v[nMax], ySorted[nMax];
ifstream in("cmap.in");
ofstream out("cmap.out");
bool compareX(point a, point b) {
return a.x < b.x;
}
bool compareY(point a, point b) {
return a.y < b.y;
}
double min(double a, double b) {
return (a < b ? a : b);
}
double dist(point a, point b) {
double aux;
aux = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
return aux;
}
double divide(int left, int right) {
if (right - left == 1) {
return dist(v[left], v[right]);
}
if (right - left == 2) {
return min(dist(v[left], v[right]), min(dist(v[left], v[left + 1]),dist(v[left + 1], v[right])));
}
int m = (left + right) / 2;
double leftDist = divide(left, m);
double rightDist = divide(m + 1, right);
double d = min(leftDist, rightDist);
double delta = d;
int k = 0;
for (int i = left; i <= right; i++) {
if (dist(v[i], v[m]) <= delta) {
ySorted[k++] = v[i];
}
}
sort(ySorted, ySorted + k, compareY);
for (int i = 0; i < k - 1; i++) {
for (int j = i + 1; j <= (i + 7) && j < k; j++) {
d = min(d, dist(ySorted[i], ySorted[j]));
}
}
return d;
}
int main() {
int n;
in >> n;
for (int i = 0; i < n; i++) {
in >> v[i].x >> v[i].y;
}
sort(v, v + n, compareX);
double sol = divide(0, n-1);
out << fixed << setprecision(6) << sol << endl;
return 0;
}