Pagini recente » Cod sursa (job #1275790) | Cod sursa (job #489714) | Cod sursa (job #2783698) | Cod sursa (job #972496) | Cod sursa (job #2458778)
#include <bits/stdc++.h>
using namespace std;
#define px first
#define py second
const int MAXN = 100005, EPS = 1e-9;
pair<int, int> pct[MAXN];
bool comp(pair<int, int> a, pair<int, int> b){
return a.py < b.py;
}
double calc(pair<int, int> a, pair<int, int> b){
return sqrt((a.px - b.px) * (a.px - b.px) + (a.py - b.py) * (a.py - b.py));
}
double divide(int st, int dr){
if(dr - st + 1 <= 3){
double ret = 1e9;
for(int i = st; i < dr; ++i){
double dist = calc(pct[i], pct[i + 1]);
ret = min(ret, dist);
}
return ret;
}
int mij = (st + dr) / 2;
double 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 < -EPS)
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 < min(i + 10, (int)Y.size()); ++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);
double mndist = divide(1, n);
fout << fixed << setprecision(7) << mndist;
return 0;
}