Pagini recente » Cod sursa (job #2199201) | Cod sursa (job #1688310) | Cod sursa (job #2590551) | Cod sursa (job #3208417) | Cod sursa (job #2705353)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct p
{
int x,y;
}Punct[100001];
bool cmp(p A, p B)
{
return ((A.x<B.x) || (A.x==B.x && A.y<B.y));
}
double dist(int x1, int x2, int y1, int y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
double Distanta(p Punct[], int q, int r)
{
double D;
if(r-q+1>3)
{
int mij=(q+r)/2;
D=min(Distanta(Punct,q,mij),Distanta(Punct,mij+1,r));
}
else
{
double d1,d2,d3;
switch(r-q+1)
{
case 2:
D=dist(Punct[q].x,Punct[r].x,Punct[q].y,Punct[r].y);
break;
case 3:
d1=dist(Punct[q].x,Punct[q+1].x,Punct[q].y,Punct[q+1].y);
d2=dist(Punct[q+1].x,Punct[r].x,Punct[q+1].y,Punct[r].y);
d3=dist(Punct[r].x,Punct[q].x,Punct[r].y,Punct[q].y);
D=min(d1,min(d2,d3));
break;
}
}
return D;
}
int n;
int main()
{
fin >> n;
for(int i=1;i<=n;i++)
fin >> Punct[i].x >> Punct[i].y;
sort(Punct+1,Punct+n+1,cmp);
fout << fixed << setprecision(8) << Distanta(Punct,1,n);
return 0;
}