Pagini recente » Cod sursa (job #2781150) | Cod sursa (job #2863481) | Cod sursa (job #250426) | Cod sursa (job #949509) | Cod sursa (job #2911007)
#include<bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct
{
int x,y;
}a[N],b[N];
bool comp_x(punct x,punct y)
{
return x.x<y.x;
}
bool comp_y(punct x,punct y)
{
return x.y<y.y;
}
double dist(punct x,punct y)
{
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double combine(int st, int dr, double lungime)
{
double m=lungime;
int ct=0,mij = (st+dr)/2;
for(int i=st; i<=dr; i++)
if(abs(a[i].x - a[mij].x) < lungime)
b[++ct]=a[i];
sort(b+1,b+ct+1,comp_y);
for(int i=1; i<ct; i++)
for(int j=i+1; j<=ct && j<=i+7; j++)
m= min(m,dist(b[i],b[j]));
return m;
}
double divide_et_impera(int st, int dr)
{
double m;
if(dr-st <= 2)
{
m = dist(a[st],a[st+1]);
if(dr-st == 2)
{
m= min(m, dist(a[st],a[st+2]));
m= min(m, dist(a[st+1],a[st+2]));
}
return m;
}
int mij = (st+dr)/2;
m = min(divide_et_impera(st, mij), divide_et_impera(mij+1, dr));
m = min(m, combine(st, dr, m));
return m;
}
int main()
{
int n,i;
fin>>n;
for(i=1; i<=n; i++)
fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,comp_x);
fout<<setprecision(6)<<fixed<<divide_et_impera(1, n);
return 0;
}