Pagini recente » Cod sursa (job #2443900) | Cod sursa (job #1737207) | Istoria paginii runda/test_9_10_13 | Cod sursa (job #2522465) | Cod sursa (job #2278858)
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define MOD 1000000007
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair< int , int > PII;
int n, m, cnt;
PII a[100100];
double dist(PII a, PII b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double divide(int st, int dr) {
if (dr - st <= 2) {
double d = 1e18;
for (int i = st; i < dr; i++){
for (int j = i + 1; j <= dr; j++){
d = min(d, dist(a[i], a[j]));
}
}
return d;
}
int mid = (st + dr) >> 1;
double d = min(divide(st, mid), divide(mid + 1, dr));
vector < PII > V;
for (int i = st; i <= dr; i++) {
if (abs(a[i].x - a[mid].x) <= d) V.push_back(a[i]);
}
sort(V.begin(), V.end(), [&](PII a, PII b){ return a.y > b.y; });
for (int i = 0; i < V.size(); i++)
for (int j = i + 1; j < V.size() && j - i <= 7; j++)
d = min(d, dist(V[i], V[j]));
return d;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ifstream cin("cmap.in");
ofstream cout("cmap.out");
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
}
sort(a + 1, a + n + 1);
cout << setprecision(6) << fixed << divide(1, n);
return 0;
}