Pagini recente » Cod sursa (job #1289274) | Cod sursa (job #2863249)
#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];
bool criteria(point a, point b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
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)
{
int mij = (s+d)/2;
double Min=width;
for(int i=mij; i>=s; i--)
{
if(v[mij].x-v[i].x >= width)
break;
for(int j=mij+1; j<=d; j++)
{
if(v[j].x-v[mij].x >= width)
break;
Min = min(Min, dis(i, j));
}
}
return Min;
}
double divide_et_impera(int s, int d)
{
double Min;
if(d-s <= 3)
{
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, criteria);
g<<setprecision(6)<<fixed<<divide_et_impera(1, n);
return 0;
}