Pagini recente » Cod sursa (job #2790066) | Cod sursa (job #2236882) | Cod sursa (job #1760581) | Cod sursa (job #3030743) | Cod sursa (job #2458844)
#include <bits/stdc++.h>
using namespace std;
#define px first
#define py second
const int MAXN = 100005;
pair<int, int> pct[MAXN];
bool comp(pair<int, int> a, pair<int, int> b){
return a.py < b.py;
}
long long calc(pair<int, int> a, pair<int, int> b){
return 1LL * (a.px - b.px) * (a.px - b.px) + 1LL * (a.py - b.py) * (a.py - b.py);
}
long long divide(int st, int dr){
if(dr - st + 1 <= 3){
long long ret = 1LL << 60;
for(int i = st; i <= dr; ++i){
for(int j = i + 1; j <= dr; ++j)
ret = min(ret, calc(pct[i], pct[j]));
}
return ret;
}
int mij = (st + dr) / 2;
long long mindist = min(divide(st, mij), divide(mij + 1, dr));
vector<pair<int, int> > Y;
for(int i = st; i <= dr; ++i){
if(abs(pct[i].px - pct[mij].px) < mindist)
Y.push_back(pct[i]);
}
sort(Y.begin(), Y.end(), comp);
for(int i = 0; i < (int)Y.size(); ++i){
for(int j = i + 1; j < (int)Y.size() && j - i < 8; ++j)
mindist = min(mindist, calc(Y[i], Y[j]));
}
return mindist;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> pct[i].px >> pct[i].py;
sort(pct + 1, pct + n + 1);
fout << fixed << setprecision(6) << sqrt((long double)divide(1, n));
return 0;
}