Pagini recente » Cod sursa (job #109810) | Cod sursa (job #1447165) | Cod sursa (job #37521) | Cod sursa (job #2067340) | Cod sursa (job #530419)
Cod sursa(job #530419)
#include <iostream>
#include <fstream>
#include <math.h>
#define NMAX 100001
using namespace std;
struct punct { int 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");
int pdist(punct a, punct b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int divimp(int st, int dr) //st, dr = indici
{
int i,j;
//cout << st << " " << dr << endl;
if (dr-st<=2)
if (dr-st == 1)
{
int d = pdist(p[st],p[dr]);
//cout << d << endl;
return d;
}
else
{
int d1 = pdist(p[st],p[dr]);
int d2 = pdist(p[st],p[dr-1]);
int 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;
int dst = divimp(st,mj);
int ddr = divimp(mj+1,dr);
int 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++)
{
int dx = pdist(p[i],p[j]);
if (dx < d)
d = dx;
}
//cout << st << " " << dr << " " << d << endl;
return d;
}
}
int main()
{
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 << sqrt(rez);
g.precision(8);
g << sqrt(rez);
return 0;
}