Pagini recente » Cod sursa (job #2955053) | Cod sursa (job #1819985) | Cod sursa (job #2193943) | Cod sursa (job #402108) | Cod sursa (job #2482498)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int MAXN = 1e5 + 1;
const int INF = 1e6;
double minim = INF;
struct punct{
int x, y;
};
bool cmp(punct a, punct b){
return a.x < b.x or (a.x == b.x and a.y < b.y);
}
double formula(punct a, punct b){
return (double)sqrt(double(((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y))));
}
punct v[MAXN];
punct aux[MAXN];
punct b[MAXN];
void interclasare(int st ,int mij ,int dr){
int indice1 = st - 1, indice2 = mij , indice = st - 1;
while(indice1 <= mij and indice2 <= dr){
if(v[indice1].y < v[indice2].y) aux[++indice] = v[++indice1];
else aux[++indice] = v[++indice2];
}
for(int i = indice1 ; i <= mij ; ++i)
aux[++indice] = v[i];
for(int i = indice2; i <= dr; ++i)
aux[++indice] = v[i];
for(int i = st; i <= dr; ++i)
v[i] = aux[i];
}
void dei(int st, int dr){
int m = (st + dr) / 2;
if(dr - st <= 2){
for(int i = st ; i <= dr - 1; ++i){
for(int j = i + 1; j <= dr; ++j){
minim = min(minim, formula(v[i], v[j]));
}
}
return;
}
dei(st, m); dei(m + 1, dr);
interclasare(st, m, dr);
int indice = 0;
for(int i = st; i <= dr; ++i)
if(abs(v[i].x - v[m].x) <= minim)
b[++indice] = v[i];
for(int i = 1; i <= indice - 7; ++i)
for(int j = i + 1; j <= min(indice, i + 7) ; ++j)
minim = min(minim, formula(b[i], b[j]));
}
int main(){
ios::sync_with_stdio(false);
fin.tie(0);fout.tie(0);
int n ;
fin >> n;
for(int i = 1; i <= n ;++i)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
dei(1, n);
fout << setprecision(6) << fixed << minim;
return 0;
}