Pagini recente » Cod sursa (job #624745) | Cod sursa (job #1539785) | Cod sursa (job #624764) | Cod sursa (job #2915746) | Cod sursa (job #2071711)
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
struct punct
{
int x,y;
};
double distEuclid(punct a, punct b) {
double x = a.x - b.x;
double y = a.y - b.y;
double dist;
dist = pow(x, 2) + pow(y, 2);
dist = sqrt(dist);
return dist;
}
bool cmp1(punct a,punct b)
{
return a.x < b.x;
}
bool cmp2(punct a,punct b)
{
return a.y < b.y;
}
vector<punct> X;
vector<punct> Y;
double DivImp(int st,int dr,vector<punct> Y)
{
if(dr-st < 4)
{
double minim = distEuclid(X[st],X[dr]);
for(int i=st; i<dr; i++)
for(int j=i+1; j<=dr; j++)
if(distEuclid(X[i],X[j]) < minim)
minim = distEuclid(X[i],X[j]);
return minim;
}
else
{
int mij = (st+dr) / 2;
vector<punct> SY;
vector<punct> DY;
for(int i=0; i<Y.size(); i++)
{
if(Y[i].x <= X[mij].x)
SY.push_back(Y[i]);
if(Y[i].x > X[mij].x)
DY.push_back(Y[i]);
}
double d1 = DivImp(st,mij,SY);
double d2 = DivImp(mij+1,dr,DY);
double d = min(d1,d2);
vector<punct> LY;
for(int i=1; i<=Y.size(); i++)
if(abs(Y[i].x - X[mij].x) <= d)
LY.push_back(Y[i]);
double d3 = distEuclid(LY[0],LY[LY.size()-1]);
for(int i=0; i<LY.size()-1; i++)
for(int j=i+1; j<LY.size(); j++)
if(distEuclid(LY[i],LY[j]) < d3)
d3 = distEuclid(LY[i],LY[j]);
d = min(d,d3);
return d;
}
}
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
{
punct t;
cin>>t.x>>t.y;
X.push_back(t); Y.push_back(t);
}
sort(X.begin(),X.end(),cmp1);
sort(Y.begin(),Y.end(),cmp2);
double dist = DivImp(0,n-1,Y);
cout<<dist<<endl;
return 0;
}