Pagini recente » Cod sursa (job #1207795) | Cod sursa (job #1676747) | Cod sursa (job #542038) | Cod sursa (job #3248464) | Cod sursa (job #2089084)
#include <bits/stdc++.h>
using namespace std;
#define Punct pair<double, double>
#define X first
#define Y second
#define NMAX 100005
double sqr(double x) { return x * x; }
Punct px[NMAX];
Punct py[NMAX];
int n;
bool dupaX(Punct a, Punct b) {
if (a.X == b.X)
return a.Y < b.Y;
return a.X < b.X;
}
bool dupaY(Punct a, Punct b) {
if (a.Y == b.Y)
return a.X < b.X;
return a.Y < b.Y;
}
void citire() {
scanf("%d ", &n);
for (int i = 0; i < n; i++) {
double x, y;
scanf("%lf %lf ", &x, &y);
px[i] = { x, y };
py[i] = { x, y };
}
sort(px, px + n, dupaX);
sort(py, py + n, dupaY);
}
double dist(Punct a, Punct b) {
return sqr(a.X - b.X) + sqr(a.Y - b.Y);
}
double brut(Punct p[], int n) {
double result = FLT_MAX;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (dist(p[i], p[j]) < result)
result = dist(p[i], p[j]);
}
}
return result;
}
double minRamase(Punct ramase[], int n, double d) {
double res = d;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n && (ramase[j].Y - ramase[i].Y) < res; j++) {
double dd = dist(ramase[i], ramase[j]);
res = min(res, dd);
}
}
return res;
}
double divide(Punct px[], Punct py[], int n) {
// STEP 1:
if (n < 3)
return brut(px, n);
int mij = n / 2;
Punct mp = px[mij];
Punct pLeft[mij + 1], pRight[n - mij - 1];
int pl = 0, pr = 0;
for (int i = 0; i < n; i++) {
if(py[i].X <= mp.X)
pLeft[pl++] = py[i];
else pRight[pr++] = py[i];
}
// STEP 2
double d = min(divide(px, pLeft, mij), divide(px + mij, pRight, n - mij));
// STEP 3
Punct ramase[n];
int ramaseDim = 0;
for (int i = 0; i < n; i++) {
if (abs(py[i].X - mp.X) < d)
ramase[ramaseDim++] = py[i];
}
// STEP 4 (done at beginning)
// STEP 5 and 6
return min(d, minRamase(ramase, ramaseDim, d));
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
citire();
cout << fixed << sqrt(divide(px, py, n));
return 0;
}