Pagini recente » Cod sursa (job #3241239) | Cod sursa (job #2551045) | Cod sursa (job #1156038) | Cod sursa (job #1949440) | Cod sursa (job #2469342)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#define DIM 100010
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
long long n, i, x, y;
vector <pair <long long, long long> > p;
pair <long long, long long> r[DIM], q[DIM];
long long distanta (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);
}
void interclasare(long long st, long long mid, long long dr) {
long long i, j, k;
i = st;
j = mid + 1;
k = 0;
while (i<=mid && j<=dr)
if (p[i].second < p[j].second) {
r[++k] = p[i++];
} else {
r[++k] = p[j++];
}
for (; i<=mid; i++)
r[++k] = p[i];
for (; j<=dr; j++)
r[++k] = p[j];
for (k=1, i=st; i<=dr; i++, k++)
p[i] = r[k];
}
long long jas(long long st, long long dr){
long long k;
if (dr - st == 1){
k = distanta (p[st], p[dr]);
interclasare (st, st, dr);
return k;
}
if (dr - st == 2){
k = min (distanta (p[st], p[st+1]), min(distanta (p[st+1], p[dr]), distanta (p[st], p[dr])));
interclasare (st, st, st+1);
interclasare (st, st+1, dr);
return k;
}
long long mid = (st + dr)/2;
long long kst = jas (st, mid);
long long kdr = jas (mid + 1, dr);
interclasare (st, mid, dr);
long long minim = min (kst, kdr);
long long t = 0;
for (long long i=st; i<=dr; i++){
if (abs(p[mid].first - p[i].first) <= minim){
q[++t] = p[i];
}
}
for (long long i=1; i<t; i++) {
for (long long j=i+1; j<=t && j<=i+7; j++)
minim = min (minim, distanta(q[i], q[j]));
}
return minim;
}
int main(){
fin >> n;
for (i=1; i<=n; i++){
fin >> x >> y;
p.push_back(make_pair(x,y));
}
sort (p.begin(), p.end());
fout << setprecision(7) << fixed << (double)sqrt(jas(1,n));
return 0;
}