Pagini recente » Cod sursa (job #1118015) | Cod sursa (job #894951) | Cod sursa (job #1544780) | Cod sursa (job #2281475) | Cod sursa (job #552926)
Cod sursa(job #552926)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define nmax 100001
long n, mij, q;
double S = 1000000000;
struct punct
{
long x, y;
}p[nmax], pp[nmax];
punct D;
void citire()
{
freopen("cmap.in","r",stdin); scanf("%ld", &n);
for(long i=1; i<=n; i++)
scanf("%ld %ld", &p[i].x, &p[i].y);
}
void afisare()
{
printf("%.6lf", S);
}
bool cmpx(punct a, punct b)
{
return a.x < b.x;
}
bool cmpy(punct a, punct b)
{
return a.y < b.y;
}
void d_coord()
{
mij = n/2;
D.x = p[mij].x;
}
double euclid(long i, long j)
{
return sqrt( pow(p[i].x-p[j].x, double(2)) + pow(p[i].y-p[j].y, double(2)) );
}
void det_int()
{
q = 0;
for(long i=1; i<=n; i++)
if(p[i].x <= D.x+S && p[i].x >= D.x-S)
pp[++q] = p[i];
sort(pp+1, pp+1+q, cmpy);
}
void wtf(long l, long r)
{
long mij;
if(r-l <= 2)
{
S = min(S, euclid(l, l+1));
if(r-l == 2)
S = min(S, min(euclid(l,r), euclid(l+1, r)) );
}
else
{
mij = (l+r)/2;
wtf(l,mij); wtf(mij,r);
}
det_int(); // punctele din intervalul 2*S
//printf("%.6lf\n", S);
double dt;
for(long i=1; i<=q; i++)
for(long j=i+1; j<=i+7 && j<=q; j++)
{
dt = euclid(i, j);
if(dt < S)
S = dt;
}
}
void solve()
{
sort(p+1, p+1+n, cmpx); // sortat abscisa
d_coord(); // coord. dreptei D
}
int main()
{
citire();
freopen("cmap.out","w",stdout);
solve();
wtf(1, n);
afisare();
return 0;
}