Pagini recente » Cod sursa (job #1726551) | Cod sursa (job #2065730) | Cod sursa (job #1501532) | Cod sursa (job #3005158) | Cod sursa (job #2067958)
#include<fstream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iomanip>
#define INF 999999999
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
class point
{
double x,y;
public:
double read_point()
{
f>>x>>y;
return x;
}
double write_point()
{
g<<x<<" "<<y<<"\n";
return x;
}
double getx()
{
return x;
}
double gety()
{
return y;
}
}X,Y;
double dist_min=INF;
bool cmpx(point A, point B)
{
return A.getx()<B.getx();
}
bool cmpy(point A, point B)
{
return A.gety()<B.gety();
}
double euclid_dist(point A, point B)
{
double d1,d2;
d1=A.getx()-B.getx();
d2=A.gety()-B.gety();
return sqrt((d1*d1)+(d2*d2));
}
double get_min(double a, double b)
{
if(a<=b) return a;
else return b;
}
double get_pair_of_points(point l[],int st,int dr)
{
if(dr-st<3)
{
double dist_min=INF;
for(int i=st;i<dr;++i)
for(int j=i+1;j<=dr;++j)
{
double distanta=euclid_dist(l[i],l[j]);
if(distanta<dist_min)
{
X=l[i];
Y=l[j];
dist_min=distanta;
}
}
return dist_min;
}
else
{
int mid=(st+dr)/2;
double line_L;
line_L=(l[mid].getx()+l[mid+1].getx())/2;
double dist_left=get_pair_of_points(l,st,mid);
double dist_right=get_pair_of_points(l,mid+1,dr);
double dist_minim=get_min(dist_left,dist_right);
vector <point> lista_Y;
int nr_Y=0;
for(int i=st;i<=dr;++i)
if(fabs(line_L-l[i].getx())>dist_minim)
{
lista_Y.push_back(l[i]);
nr_Y++;
}
sort(lista_Y.begin(),lista_Y.end(),cmpy);
for(int i=0;i<nr_Y-1;++i)
{
int length=1;
for(int j=i+1;j<nr_Y&&length<8;++j,++length)
{
double dist_loc=euclid_dist(lista_Y[i],lista_Y[j]);
if(dist_loc<dist_minim)
{
dist_minim=dist_loc;
}
}
}
return dist_minim;
}
return -1;
}
int main()
{
int n;
f>>n;
point lista[n];
for(int i=0;i<n;++i)
{
lista[i].read_point();
}
sort(lista,lista+n,cmpx);
g<<fixed<<setprecision(6)<<get_pair_of_points(lista,0,n-1);
}