Pagini recente » Cod sursa (job #2819325) | Cod sursa (job #2145048) | Cod sursa (job #2669286) | Cod sursa (job #1180388) | Cod sursa (job #2278851)
#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], b[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 (st; st < dr; st++){
for (int j = st + 1; j <= dr; j++){
d = min(d, dist(a[st], a[j]));
}
}
return d;
}
int mid = (st + dr) >> 1;
double d = min(divide(st, mid), divide(mid + 1, dr));
{ // merge
vector < PII > V;
int p1 = st, p2 = mid + 1, p = 0;
while (p1 <= mid && p2 <= dr) {
if (b[p1].y < b[p2].y) V.push_back(b[p1++]);
else V.push_back(b[p2++]);
}
while (p1 <= mid) V.push_back(b[p1++]);
while (p2 <= dr) V.push_back(b[p2++]);
for (int i = st; i <= dr; i++) b[i] = V[p++];
}
vector < PII > V;
for (int i = st; i <= dr; i++) {
if (abs(b[i].y - a[mid].x) <= d) V.push_back(b[i]);
}
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;
b[i] = {a[i].y, a[i].x};
}
sort(a + 1, a + n + 1);
cout << setprecision(6) << fixed << divide(1, n);
return 0;
}