Pagini recente » Cod sursa (job #2118388) | Cod sursa (job #2421897) | Cod sursa (job #2551793) | Cod sursa (job #2980022) | Cod sursa (job #1071077)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define Nmax 100010
#define INF 1000000010
using namespace std;
struct punct
{
long long x, y;
} Px[Nmax], Py[Nmax];
int n;
long long i, Ny, mij, p, j;
int poz[Nmax];
double cmp_x (long long a, long long b)
{
return Px[a].x < Px[b].x;
}
double cmp_y (punct a, punct b)
{
return a.y < b.y;
}
double dist (double x1, double y1, double x2, double y2)
{
return sqrt ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double Dmin (int st, int dr)
{
double dmin = INF, d;
if (dr - st + 1 <= 3)
{
if (dr - st + 1 >= 2)
dmin = dist ( Px[ poz[st] ].x, Px[ poz[st] ].y, Px[ poz[st + 1] ].x, Px[ poz[st + 1] ].y );
if (dr - st + 1 == 3) {
d = dist ( Px[ poz[st] ].x, Px[ poz[st] ].y, Px[ poz[st + 2] ].x, Px[ poz[st + 2] ].y );
if (d < dmin) dmin = d;
d = dist ( Px[ poz[st + 2] ].x, Px[ poz[st + 2] ].y, Px[ poz[st + 1] ].x, Px[ poz[st + 1] ].y );
if (d < dmin) dmin = d;
}
return dmin;
}
dmin = Dmin (st, (dr + st) >> 1);
d = Dmin (((dr + st) >> 1) + 1, dr);
if (d < dmin) dmin = d;
mij = (st + dr) >> 1; Ny = 0;
for (i = st; i <= dr; i++)
if ( abs (Px[poz[mij]].x - Px[poz[i]].x) <= dmin )
Py[++Ny] = Px[poz[i]];
sort (Py + 1, Py + Ny + 1, cmp_y);
for (i = 2, p = 1; i <= Ny; i++) {
while (Py[i].y - Py[p].y > dmin)
p++;
for (j = p; j < i; j++) {
d = dist (Py[i].x, Py[i].y, Py[j].x, Py[j].y);
if (d < dmin) dmin = d;
}
}
return dmin;
}
int main ()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
in>>n;
for (i = 1; i <= n; i++)
{
in>>Px[i].x>>Px[i].y;
poz[i] = i;
}
sort (poz + 1, poz + n + 1, cmp_x);
cout<<setprecision(8)<<Dmin (1, n);
return 0;
}