Pagini recente » Cod sursa (job #971174) | Cod sursa (job #248654) | Cod sursa (job #3219050) | Cod sursa (job #678598) | Cod sursa (job #2074191)
#include<fstream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iomanip>
#include<iostream>
#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;
}
bool setxy(int a,int b)
{
x=a;
y=b;
return true;
}
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, point ly[])
{
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;
point Px[mid+1],Py[dr-mid-1];
int nl=0;
int nr=0;
for(int i=st;i<=dr;++i)
{
if(ly[i].getx()<=line_L)
{
Px[nl].setxy(ly[i].getx(),ly[i].gety());
++nl;
}
else
{
Py[nr].setxy(ly[i].getx(),ly[i].gety());
++nr;
}
}
double dist_left=get_pair_of_points(l,st,mid,Px);
double dist_right=get_pair_of_points(l,mid+1,dr,Py);
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-ly[i].getx())>dist_minim)
{
lista_Y.push_back(ly[i]);
nr_Y++;
}
for(int i=0;i<nr_Y-1;++i)
{
for(int j=i+1;j<nr_Y&&j-i<8;++j)
{
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];
point ly[n];
for(int i=0;i<n;++i)
{
lista[i].read_point();
ly[i].setxy(lista[i].getx(),lista[i].gety());
}
sort(lista,lista+n,cmpx);
sort(ly,ly+n,cmpy);
g<<fixed<<setprecision(6)<<get_pair_of_points(lista,0,n-1,ly);
}