Pagini recente » Cod sursa (job #2401645) | Cod sursa (job #3222693) | Cod sursa (job #3200260) | Cod sursa (job #1448948) | Cod sursa (job #2103849)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <limits.h>
#include <vector>
#include <math.h>
#include <cstdio>
#include <stdlib.h>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
int x;
int y;
};
vector <punct> v;
bool comp_x(punct a, punct b)
{
return a.x<b.x;
}
bool comp_y(punct a, punct b)
{
return a.y<b.y;
}
long long dist2(punct a, punct b)
{ long long x=(long long) (a.x - b.x);
long long y=(long long) (a.y - b.y);
return x*x+y*y;
}
long long distanta (int prim, int ultim)
{
int i,j;
vector <punct> temp;
if(ultim-prim==1)
return dist2(v[prim],v[ultim]);
if(ultim-prim==2)
return min( dist2(v[prim], v[prim+1]), min ( dist2(v[prim+1],v[prim+2]), dist2(v[prim+2],v[prim] ) ) );
int mij=(prim+ultim)/2;
long long d1=distanta(prim,mij);
long long d2=distanta(mij+1,ultim);
long long dist_min=min(d1,d2);
for(i=prim; i<=ultim; i++)
{
if(((v[i].x-v[mij].x)*(v[i].x-v[mij].x)) <=dist_min )
temp.push_back(v[i]);
}
long long d;
sort(temp.begin(), temp.end(), comp_y);
for(i=0; i<temp.size(); i++)
for(j=i+1; j<=i+7 && j<temp.size(); j++)
{
d=dist2(temp[i],temp[j]);
dist_min=min(dist_min,d);
}
return dist_min;
}
int main()
{
int n;
f>>n;
punct p;
int i;
for(i=0; i<n; i++)
{
f>>p.x>>p.y;
v.push_back(p);
}
sort(v.begin(),v.end(),comp_x);
/*for(i=0; i<v.size(); i++)
cout<<v[i].x<<" "<<v[i].y<<endl;*/
g<<fixed<<setprecision(6)<<sqrt(distanta(0,n-1));
// cout<<fixed<<setprecision(6)<<sqrt(distanta(0,n-1));
return 0;
}