Pagini recente » Cod sursa (job #2591314) | Cod sursa (job #383740) | Cod sursa (job #2154766) | Cod sursa (job #2028040) | Cod sursa (job #2068514)
#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
{
long long x,y;
public:
long long read_point()
{
f>>x>>y;
return x;
}
long long write_point()
{
g<<x<<" "<<y<<"\n";
return x;
}
long long getx()
{
return x;
}
long long gety()
{
return y;
}
}X,Y;
long long 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();
}
long long euclid_dist(point A, point B)
{
long long d1,d2;
d1=A.getx()-B.getx();
d2=A.gety()-B.gety();
return (d1*d1)+(d2*d2);
}
long long get_min(long long a, long long b)
{
if(a<=b) return a;
else return b;
}
long long get_pair_of_points(point l[],int st,int dr)
{
if(dr-st<3)
{
long long dist_min=INF;
for(int i=st;i<dr;++i)
for(int j=i+1;j<=dr;++j)
{
long long 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;
long long line_L;
line_L=(l[mid].getx()+l[mid+1].getx())/2;
long long dist_left=get_pair_of_points(l,st,mid);
long long dist_right=get_pair_of_points(l,mid+1,dr);
long long 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)
{
long long 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)<<sqrt(get_pair_of_points(lista,0,n-1));
}