Pagini recente » Cod sursa (job #3203405) | Cod sursa (job #3142564) | Cod sursa (job #3121633) | Cod sursa (job #3276427) | Cod sursa (job #3219166)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct Punct {
long long x, y;
}v[100005];
long long dist(Punct a, Punct b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool cmpx(Punct a, Punct b) {
return a.x < b.x;
}
bool cmpy(Punct a, Punct b) {
return a.y < b.y;
}
int n;
long long divet(int st, int dr) {
if (st + 1 == dr) {
return dist(v[st], v[dr]);
}
else if (st + 2 == dr) {
return min(min(dist(v[st], v[st + 1]), dist(v[st + 1], v[st + 2])), dist(v[st], v[st + 2]));
}
int mij = (st + dr) / 2;
long long l = min(divet(st, mij), divet(mij + 1, dr));
vector < Punct > pct;
for (int i = st; i <= dr; i++) {
if ((v[i].x - v[mij].x) * (v[i].x - v[mij].x) < l) pct.push_back(v[i]);
}
sort(pct.begin(), pct.end(), cmpy);
for (int i = 0; i < pct.size(); i++) {
for (int j = i + 1; j < pct.size(); j++) {
if (abs(v[i].y - v[j].y) >= l) break;
l = min(l , dist(v[i], v[j]));
}
}
return l;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++) {
f >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmpx);
g << fixed << setprecision(6) << sqrt(divet(1, n));
return 0;
}