Pagini recente » Cod sursa (job #3349523) | Cod sursa (job #3339618) | Cod sursa (job #3307162) | Cod sursa (job #806506) | Cod sursa (job #3307155)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
const int NMAX = 100000;
using ll = long long;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
struct puncte{
ll x, y;
bool operator <(const puncte & rhs) const {
if(x != rhs.x)
return x < rhs.x;
return x < rhs.y;
}
}v[NMAX + 2];
bool cmp(const puncte &a, const puncte &b) {
if(a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
long double ans = 2e9 * sqrt(2);
long double dist(puncte a, puncte b) {
return 1LL * sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}
void divide(int st, int dr) {
if(st + 1 >= dr) {
if(st + 1 == dr)
ans = min(ans, dist(v[st], v[dr]));
return;
}
int mid = (st + dr) / 2;
divide(st, mid);
divide(mid + 1, dr);
vector <puncte> nou; ///DE SCHIMBAT FARA SORTARE
for(int i = st; i <= dr; i++) {
if((v[i].x <= v[mid].x && v[i].x + ans <= v[mid].x) ||
(v[i].x >= v[mid].x && v[i].x - ans <= v[mid].x))
nou.push_back(v[i]);
}
sort(nou.begin(), nou.end(), cmp);
long double d = ans;
for(int i = 0; i < nou.size(); i++) {
for(int j = i + 1; j < min((int)nou.size(), i + 7); j++) { ///doar urm 7
d = min(d, dist(nou[i], nou[j]));
}
}
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1);
divide(1, n);
cout << setprecision(6) << fixed << ans;
return 0;
}