Pagini recente » Cod sursa (job #1354579) | Cod sursa (job #809898) | Cod sursa (job #1845949) | Cod sursa (job #1210769) | Cod sursa (job #2458764)
#include <bits/stdc++.h>
using namespace std;
#define px first
#define py second
const int MAXN = 100005;
pair<int, int> pct[MAXN];
vector<pair<int, int> > Y;
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;
return min(divide(st, mij), divide(mij + 1, dr));
}
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 mndistrec = divide(1, n);
int d = (pct[n / 2].px + pct[n / 2 + 1].px) / 2;
for(int i = 1; i <= n; ++i){
if(abs(pct[i].px - d) <= mndistrec)
Y.push_back({pct[i].py, pct[i].px});
}
sort(Y.begin(), Y.end());
double mndistinter = 1e9;
for(int p = 0; p < (int)Y.size() - 8; ++p){
double dist1 = calc(Y[p], Y[p + 1]);
double dist2 = calc(Y[p], Y[p + 2]);
double dist3 = calc(Y[p], Y[p + 3]);
double dist4 = calc(Y[p], Y[p + 4]);
double dist5 = calc(Y[p], Y[p + 5]);
double dist6 = calc(Y[p], Y[p + 6]);
double dist7 = calc(Y[p], Y[p + 7]);
mndistinter = min(mndistinter, min(dist1, min(dist2, min(dist3, min(dist4, min(dist5, min(dist6, dist7)))))));
}
fout << fixed << setprecision(7) << min(mndistrec, mndistinter);
return 0;
}