Pagini recente » Monitorul de evaluare | Cod sursa (job #240400) | Cod sursa (job #561290) | Cod sursa (job #2775397) | Cod sursa (job #2377979)
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <limits>
using namespace std;
#define x first
#define y second
#define NMAX 100005
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
pair<int, int> a;
vector<pair<int, int> > pct;
vector<pair<int, int> > aux(NMAX), check(NMAX);
long double dist(pair<int, int> i, pair<int, int> j) {
return sqrt(1LL * (j.x - i.x) * (j.x - i.x) + 1LL * (j.y - i.y) * (j.y - i.y));
}
void interclass(int l, int mij, int r) {
int i = l, j = mij + 1, k = 0;
while (k < r - l + 1) {
if (i > mij || (j <= r && pct[i].y > pct[j].y)) {
aux[k++] = pct[j++];
} else {
aux[k++] = pct[i++];
}
}
for (i = l, k = 0 ; i <= r ; i++, k++)
pct[i] = aux[k];
}
long double closestPoints(int l, int r) {
int mij = (l + r) / 2, i, j;
long double minDist = std::numeric_limits<double>::max(), minL, minR;
if (r - l <= 2) {
for (i = l ; i < r ; i++)
for (j = i + 1 ; j <= r ; j++)
minDist = min(minDist, dist(pct[i], pct[j]));
for (i = l ; i < r ; i++)
for (j = i + 1 ; j <= r ; j++)
if (pct[i].y > pct[j].y)
swap(pct[i], pct[j]);
return minDist;
}
minL = closestPoints(l, mij);
minR = closestPoints(mij + 1, r);
minDist = min(minL, minR);
interclass(l, mij, r);
int siz = 0;
for (i = l ; i <= r ; i++) {
if (abs(pct[i].x - pct[mij].x) <= minDist) {
check[siz++] = pct[i];
}
}
for (i = 0 ; i < siz ; i++) {
for (j = i + 1 ; j < min(i + 8, siz) ; j++) {
minDist = min(minDist, dist(check[i], check[j]));
}
}
return minDist;
}
int main() {
fin >> n;
for (int i = 0 ; i < n ; i++) {
fin >> a.x >> a.y;
pct.push_back(a);
}
sort(pct.begin(), pct.end());
fout << fixed << setprecision(7) << closestPoints(0, n - 1);
}