Pagini recente » Cod sursa (job #2093138) | Cod sursa (job #1056094) | Cod sursa (job #1495245) | Cod sursa (job #1616966) | Cod sursa (job #2924376)
#include <bits/stdc++.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
pair < int , int > v[100005],k[100005];
bool cmp(pair < int , int > a, pair < int , int > b) {
return a.second>b.second;
}
void citire() {
f >> n;
for (int i=1;i<=n;i++) {
f >> v[i].first >> v[i].second;
}
sort(v+1,v+n+1);
}
double dist(int p1, int p2) {
int k1 = (v[p1].first-v[p2].first);
int k2 = (v[p1].second-v[p2].second);
return sqrt(k1*k1+k2*k2);
}
double dist2(int p1, int p2) {
int k1 = (k[p1].first-k[p2].first);
int k2 = (k[p1].second-k[p2].second);
return sqrt(k1*k1+k2*k2);
}
double divide(int st, int dr) {
if (st+1==dr) return dist(st,dr);
if (st+2==dr) return min(dist(st,st+1),min(dist(st+1,dr),dist(st,dr)));
int mij = (st+dr)/2;
double dmin = min(divide(st,mij),divide(mij+1,dr));
int ind = mij, aa = 0;
while (ind && v[mij].first-v[ind].first<=dmin) {
k[++aa]=v[ind];
ind--;
}
ind = mij+1;
while (ind<=n && v[ind].first-v[mij].first<=dmin) {
k[++aa]=v[ind];
ind++;
}
sort(k+1,k+aa+1,cmp);
for (int i=1;i<=aa-7;i++) {
for (int p=i+1;p<=i+7;p++) {
dmin = min(dmin,dist2(i,p));
}
}
return dmin;
}
int main()
{
citire();
g << fixed << setprecision(6) << divide(1,n);
return 0;
}