Pagini recente » Cod sursa (job #979433) | Cod sursa (job #2201980) | Cod sursa (job #1396232) | Cod sursa (job #1744720) | Cod sursa (job #3323916)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Punct {
long long x, y;
};
Punct v[102], vv[102];
long long n, i;
static inline long long Dist(Punct a, Punct b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
static inline bool Cmp(Punct a, Punct b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
static inline int DEI(int st, int dr) {
cout << st << " " << dr << "\n";
if(dr - st < 1) return LLONG_MAX;
else if(dr - st == 1) {
if(!Cmp(vv[st], vv[st + 1])) swap(vv[st], vv[st + 1]);
return Dist(v[st], v[st + 1]);
}
long long mij = st + (dr - st) / 2;
long long rasp = min(DEI(st, mij), DEI(mij + 1, dr));
sort(vv + st, vv + dr + 1, Cmp);
vector<Punct> sel;
for(long long i = st; i <= dr; i++) {
if(abs(vv[i].y - v[mij].x) <= rasp) sel.push_back(vv[i]);
}
for(long long i = 0; i < sel.size() - 1; i++) {
for(long long j = i + 1; j < sel.size() && j - i < 8; j++) {
rasp = min(rasp, Dist(sel[i], sel[j]));
}
}
return rasp;
}
int main() {
fin.tie(NULL);
fout.tie(NULL);
fin >> n;
for(i = 1; i <= n; i++) fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, Cmp);
for(i = 1; i <= n; i++) vv[i] = {v[i].y, v[i].x};
fout << setprecision(6) << fixed << sqrt(DEI(1, n)) << "\n";
return 0;
}