Pagini recente » Cod sursa (job #844367) | Cod sursa (job #1286412) | Cod sursa (job #2350866) | Cod sursa (job #2308957) | Cod sursa (job #1046749)
#include <iostream>
#include <fstream>
#define maxn 100001
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define INF 1<<30
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct{
int 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 j,q,cont=1;
double rez;
punct Z[10000];
if (st>=dr)
return INFINITY;
if(st+1 == dr)
return dist(X[st],X[dr]);
int mij = (st+dr)/2;
rez = INFINITY;
rez = min(rez,DivConq(st,mij));
rez = min(rez,DivConq(mij+1,dr));
//double rez = min(DivConq(st,mij),DivConq(mij+1,dr));
for(int 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(int 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);
g << setprecision(8) << DivConq(1,n);
return 0;
}