Pagini recente » Cod sursa (job #760605) | Cod sursa (job #2403127) | Cod sursa (job #2539248) | Cod sursa (job #2678798) | Cod sursa (job #1075236)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream f ("cmap.in");
ofstream g ("cmap.out");
struct punct {int x,y;} ;
punct p[100001];
int operator < (punct a, punct b)
{
if (a.x < b.x)
return 1;
else
return 0;
}
/*
int comp(punct a, punct b)
{
if (a.x < b.x)
return 1;
else
return 0;
}
*/
int n, i;
double dist(punct a, punct b)
{
double ax=a.x,bx=b.x,ay=a.y,by=b.y;
return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}
double ddcmap(int pst, int pdr)
{
if (pdr-pst<=2)
if (pdr-pst == 1)
return dist(p[pdr],p[pst]);
else
{
double d1 = dist(p[pst],p[pst+1]);
double d2 = dist(p[pst],p[pdr]);
double d3 = dist(p[pdr],p[pst+1]);
return min(min(d1,d2),d3);
}
else
{
int m= (pst+pdr)/2,i;
double s1 = ddcmap(pst, m);
double s2 = ddcmap(m+1, pdr);
double smin = min(s1,s2);
for (i=m;1;i++)
{
if (p[i].x > p[m].x+smin)
break;
}
int p2 = i-1;
for (i=m;1;i--)
{
if (p[i].x < p[m].x - smin)
break;
}
int p1 = i+1;
for(int i=p1; i <=m ; i++)
for(int j=m+1; j<=p2; j++)
{
double d1 = dist(p[i],p[j]);
if(d1<smin)
smin=d1;
}
return smin;
}
}
int main()
{
f >> n;
for(i=0; i<n; i++)
f >> p[i].x >> p[i].y;
sort(p,p+n);
for (i=0;i<n;i++)
cout << p[i].x << ' ' << p[i].y << " ";
double rez = ddcmap(0,n-1);
g.precision(18);
g<<rez << endl;
cout.precision(18);
cout << rez << endl;
return 0;
}