Pagini recente » Cod sursa (job #165893) | Cod sursa (job #208434) | Cod sursa (job #1359196) | Cod sursa (job #2938705) | Cod sursa (job #2103787)
#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;
vector <punct> temp;
bool comp_x(punct a, punct b)
{
return a.x<b.x;
}
bool comp_y(punct a, punct b)
{
return a.y<b.y;
}
double dist2(punct a, punct b)
{
double x=(double)(a.x-b.x);
double y=(double)(a.y-b.y);
return x*x+y*y;
}
double distanta (int prim, int ultim)
{ int i,j;
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;
double d1=distanta(prim,mij);
double d2=distanta(mij+1,ultim);
double 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]);
}
double 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);
g<<fixed<<setprecision(6)<<sqrt(distanta(0,n-1));
return 0;
}