Pagini recente » Cod sursa (job #2008250) | Cod sursa (job #208481) | Cod sursa (job #1252591) | Cod sursa (job #2490785) | Cod sursa (job #1047001)
#include <iostream>
#include <fstream>
#define maxn 100001
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define INF 3000000000
#include <stdio.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct{
long long x,y;
};
punct X[maxn];
int n;
bool dupax(punct Q, punct R){
return Q.x < R.x;
}
bool dupay(punct Q, punct R){
return Q.y < R.y;
}
double dist(const punct &A, const punct &B){
return sqrt((A.x - B.x)*(A.x - B.x)+(A.y-B.y)*(A.y-B.y));
}
double DivConq(int st, int dr){
int i,j,q,cont=0;
double rez;
punct Z[10200];
if (st>=dr)
return INF;
if(st+1 == dr)
return dist(X[st],X[dr]);
int mij = (st+dr)/2;
rez = INF;
rez = min(rez,DivConq(st,mij));
rez = min(rez,DivConq(mij+1,dr));
for(i=st;i<=dr;++i)
if(abs(X[mij].x - X[i].x) <= rez)
Z[++cont] = X[i];
sort(Z+1, Z+1+cont,dupay);
for(i=1;i<cont;++i){
for(j = i + 1; (j <= cont) && ((j-i) < 5); ++j, ++q){
rez = min(rez,dist(Z[i],Z[j]));
}
}
return rez;
}
int main()
{
f >> n;
for(int i=1;i<=n;i++){
f >> X[i].x >> X[i].y;
}
sort(X+1,X+n+1,dupax);
freopen("cmap.out", "w", stdout);
printf("%.6lf\n",DivConq(1,n));
return 0;
}