Pagini recente » Cod sursa (job #2591769) | Cod sursa (job #1696225) | Cod sursa (job #1875770) | Cod sursa (job #1824930) | Cod sursa (job #2238234)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define DIM 100010
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
int n,i;
pair <long long,long long> v[DIM],w[DIM],d[DIM];
long long dist (pair<long long,long long> a, pair<long long, long long> b){
return (a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second);
}
long long modul (long long n){
if (n < 0)
return -n;
return n;
}
void interclasare (int st,int mid,int dr){
int i = st, j = mid+1, el = st-1;
while (i <= mid && j <= dr){
if (v[i].second <= v[j].second){
d[++el] = w[i];
i++;
}
else{
d[++el] = w[j];
j++;
}
}
for (;i<=mid;i++)
d[++el] = v[i];
for (;j<=dr;j++)
d[++el] = v[j];
for (int i=st;i<=dr;i++)
w[i] = d[i];
}
long long solve (int st, int dr){
long long rez;
if (dr - st == 1){
rez = dist (v[st],v[dr]);
interclasare (st,st,dr);
return rez;
}
if (dr - st == 2){
rez = min (dist(v[st],v[st+1]),min(dist(v[st],v[st+1]),dist(v[st+1],v[st+2])));
interclasare (st,st,dr-1);
interclasare (st,st+1,dr);
return rez;
}
int mid = (st+dr)/2;
long long rezs = solve (st,mid);
long long rezd = solve (mid+1,dr);
interclasare (st,mid,dr);
long long sol = min (rezs,rezd);
int el = 0;
for (int i=st;i<=dr;i++){
if (modul(v[mid].first - v[i].first) <= sol)
w[++el] = v[i];
}
for (int i=1;i<el;i++)
for (int j=i+1;j<=el && j<=i+7;j++)
sol = min (sol,dist(w[i],w[j]));
return sol;
}
int main (){
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].first>>v[i].second;
sort (v+1,v+n+1);
fout<<setprecision(7)<<fixed<<sqrt(solve(1,n));
return 0;
}