Pagini recente » Cod sursa (job #131788) | Cod sursa (job #1796440) | Cod sursa (job #1426967) | Cod sursa (job #2667402) | Cod sursa (job #530425)
Cod sursa(job #530425)
#include <iostream>
#include <fstream>
#include <math.h>
#define NMAX 100001
using namespace std;
struct punct { long double x,y;};
int cmp(punct a, punct b)
{
if (a.x<=b.x) return 1;
else return 0;
}
punct p[NMAX];
int n,i;
ifstream f("cmap.in");
ofstream g("cmap.out");
long double pdist(punct a, punct b)
{
return sqrtl((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
long double divimp(int st, int dr) //st, dr = indici
{
int i,j;
//cout << st << " " << dr << endl;
if (dr-st<=2)
if (dr-st == 1)
{
long double d = pdist(p[st],p[dr]);
//cout << d << endl;
return d;
}
else
{
long double d1,d2,d3;
d1 = pdist(p[st],p[dr]);
d2 = pdist(p[st],p[dr-1]);
d3 = pdist(p[st+1],p[dr]);
//cout << st << " " << dr << " " << d1 << " " << d2 << " " << d3 << " " << endl;
if (d1 <= d2 && d1 <= d3) return d1;
if (d2 <= d1 && d2 <= d3) return d2;
return d3;
}
else
{
int mj = (st+dr)/2;
long double dst = divimp(st,mj);
long double ddr = divimp(mj+1,dr);
long double d = min(dst,ddr);
for (i=mj-1;i>=0;i--)
if (p[mj].x - p[i].x > d)
break;
int limst = i+1;
for (i=mj+1;i<n;i++)
if (p[i].x - p[mj].x > d)
break;
int limdr = i-1;
//cout << d << " " << limst << " " << limdr << endl;
for (i=limst;i<=mj;i++)
for (j=mj+1;j<=limdr;j++)
{
long double dx = pdist(p[i],p[j]);
if (dx < d)
d = dx;
}
//cout << st << " " << dr << " " << d << endl;
return d;
}
}
int main()
{
long double rez;
f >> n;
for (i=0;i<n;i++)
f>>p[i].x>>p[i].y;
sort(p,p+n,cmp);
rez = divimp(0,n-1);
cout.precision(8);
cout << rez;
g.precision(8);
g << rez;
return 0;
}