Pagini recente » Cod sursa (job #282428) | Cod sursa (job #2864546)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct point
{
int x,y;
}v[100005];
int u[100005];
bool by_x(point a, point b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
bool by_y(int a, int b)
{
if(v[a].y == v[b].y)
return v[a].x < v[b].x;
return v[a].y < v[b].y;
}
double dis(int a, int b)
{
long long x1 = v[a].x;
long long x2 = v[b].x;
long long y1 = v[a].y;
long long y2 = v[b].y;
long long x = (x1 - x2)*(x1 - x2);
long long y = (y1 - y2)*(y1 - y2);
return sqrt(x + y);
}
double combine(int s, int d, double width)
{
double Min=width;
int nr = 0, mij = (s+d)/2;
for(int i=s; i<=d; i++)
if(abs(v[i].x - v[mij].x) < width)
u[nr++] = i;
sort(u, u+nr, by_y);
for(int i=0; i<nr; i++)
for(int j=i+1; j<nr && j<=i+7; j++)
Min = min(Min, dis(u[i], u[j]));
return Min;
}
double divide_et_impera(int s, int d)
{
double Min;
if(d-s <= 2)
{
Min = dis(s, s+1);
if(d-s == 2)
{
Min = min(Min, dis(s, s+2));
Min = min(Min, dis(s+1, s+2));
}
return Min;
}
int mij = (s+d)/2;
Min = min(divide_et_impera(s, mij), divide_et_impera(mij+1, d));
Min = min(Min, combine(s, d, Min));
return Min;
}
int main()
{
int n,i;
f>>n;
for(i=1; i<=n; i++)
{
f>>v[i].x;
f>>v[i].y;
}
sort(v+1, v+1+n, by_x);
g<<setprecision(6)<<fixed<<divide_et_impera(1, n);
return 0;
}