Pagini recente » Cod sursa (job #1318206) | Cod sursa (job #638880) | Cod sursa (job #63632) | Cod sursa (job #2387246) | Cod sursa (job #2377966)
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <limits>
#include <iostream>
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);
long double dist(int i, int j) {
return sqrt((pct[j].x - pct[i].x) * (pct[j].x - pct[i].x) + (pct[j].y - pct[i].y) * (pct[j].y - pct[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(i, 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]);
cout << minDist << '\n';
return minDist;
}
minL = closestPoints(l, mij);
cout << minL << '\n';
minR = closestPoints(mij + 1, r);
cout << minR << '\n';
interclass(l, mij, r);
minDist = min(minL, minR);
for (i = l ; i <= r ; i++) {
for (j = i + 1 ; j <= min(i + 7, r) ; j++) {
minDist = min(minDist, dist(i, 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(6) << closestPoints(0, n - 1);
}