Pagini recente » Cod sursa (job #2602945) | Cod sursa (job #381642) | Cod sursa (job #1633283) | Cod sursa (job #795170) | Cod sursa (job #2490573)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
vector< pair<ll, ll> > x, y;
vector< pair<ll, ll> > v(100002);
ll getDist(pair<ll, ll> &a, pair<ll, ll> &b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
ll solve(int st, int dr)
{
if(dr - st <= 1){
return 10e18;
}
if(dr - st == 2){
if (y[st] > y[st + 1])
swap(y[st], y[st + 1]);
return getDist(x[st], x[st + 1]);
}
ll mid = (st + dr) / 2;
ll result = min(solve(st, mid), solve(mid, dr));
sort(y.begin() + st, y.begin() + dr);
ll k = 0;
for (int i = st; i < dr; i++)
if (abs(y[i].second - x[mid].first) <= result)
v[k++] = y[i];
for (int i = 0; i < k - 1; i++) {
for (int j = i + 1; j < k && j - i < 8; j++)
result = min(result, getDist(v[i], v[j]));
}
return result;
}
int main()
{
int n;
f>>n;
x.resize(n); y.resize(n);
for(int i = 0 ; i < n ; i++){
f>>x[i].first>>x[i].second;
}
sort(x.begin(), x.end());
for(int i = 0 ; i < n ; i++){
y[i].second = x[i].first;
y[i].first = x[i].second;
}
ll sol = solve(0, n);
g<<fixed<<setprecision(6)<<sqrt(sol);
return 0;
}