Pagini recente » Cod sursa (job #1462839) | Cod sursa (job #559548) | Cod sursa (job #983934) | Cod sursa (job #1344431) | Cod sursa (job #552633)
Cod sursa(job #552633)
#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()
{
freopen("cmap.out","w",stdout);
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 calc_dist(long pi, long ps)
{
double dt;
for(long i=pi; i<ps; i++)
for(long j=i+1; j<=ps; j++)
{
dt = euclid(i, j);
if(dt < S)
S = dt;
}
}
void det_int()
{
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(int l, int r)
{
double best;
if(r-l <= 2)
{
best = euclid(l, l+1);
if(r-l == 2)
best = min(best, min(euclid(l,r), euclid(l+1, r)) );
}
}
void solve()
{
sort(p+1, p+1+n, cmpx); // sortat abscisa
d_coord(); // coord. dreptei D
wtf(1, n);
//calc_dist(1, mij); calc_dist(mij+1, n); // minimul din stanga si dreapta
det_int(); // punctele din intervalul 2*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;
}
}
int main()
{
citire();
solve();
afisare();
return 0;
}