Pagini recente » Cod sursa (job #2747832) | Cod sursa (job #1992726) | Cod sursa (job #2638976) | Cod sursa (job #1792375) | Cod sursa (job #2069203)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <vector>
#include <iomanip>
using namespace std;
struct punct
{
int x,y;
}X, dreapta;
vector <punct> v,y;
int n,i,j;
double s=1000000000,smin1=1000000000,smin2=1000000000, smin=1000000000, s1=1000000000, s2=1000000000, s3=1000000000;
ifstream f("cmap.in");
ofstream g("cmap.out");
double Euclid (punct A , punct B)
{
return (sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)));
}
bool comparare (punct A, punct B)
{
return ((A.x<B.x) || (A.x==B.x) && (A.y<B.y));
}
bool comp (punct A, punct B)
{
return (A.y<B.y);
}
void SolutieS(int st, int dr) //apelul recursiv pt partea stanga
{
if((st+dr)>3){ dr=(st+dr)/2;
if((dr-st+1)==2) s=Euclid(v[st],v[dr]);
else { s1=Euclid(v[st],v[dr]);
s2=Euclid(v[st],v[st+1]);
s3=Euclid(v[st+1],v[dr]);
}
if(smin>s) smin=s;
if(smin>s1) smin=s1;
if(smin>s2) smin=s2;
if(smin>s3) smin=s3;
SolutieS(st,dr);
for(i=dr; i>=st; i--)
if(abs(v[st].x-v[i].x)<=smin) y.push_back(v[i]);
}
}
void SolutieD(int st, int dr) //apelul recursiv pt partea dreapta
{
if((dr-st+1)>3){ st=(st+dr)/2 + 1;
if((dr-st+1)==2) s=Euclid(v[st],v[dr]);
else { s1=Euclid(v[st],v[dr]);
s2=Euclid(v[st],v[st+1]);
s3=Euclid(v[st+1],v[dr]);
}
if(smin>s) smin=s;
if(smin>s1) smin=s1;
if(smin>s2) smin=s2;
if(smin>s3) smin=s3;
SolutieD(st,dr);
for(i=st; i<=dr; i++)
if(abs(v[st].x-v[i].x)<=smin) y.push_back(v[i]);
}
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>X.x>>X.y;
v.push_back(X);
}
sort(v.begin(),v.end(),comparare);
//for(vector<punct> :: iterator it=v.begin() ; it!=v.end() ; ++it)
// g<<it->x<<" ";
SolutieD(0,n-1);
SolutieS(0,n-1);
if(smin1<smin) smin=smin1;
if(smin2<smin) smin=smin2;
sort(y.begin(),y.end(),comp);
for(i=0; i<y.size(); i++)
for(j=i+1; j<y.size() && j<=i+7; j++)
if(y[i].x!=y[j].x || y[i].y!=y[j].y)
{
s=Euclid(y[i],y[j]);
if(smin>s) smin=s;
}
g<<fixed<<setprecision(6)<<smin;
f.close();
g.close();
return 0;
}