Pagini recente » Cod sursa (job #1520894) | Cod sursa (job #1024568) | Cod sursa (job #1885446) | Cod sursa (job #1693412) | Cod sursa (job #2864512)
#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 by_x(point a, point b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
bool by_y(point a, point b)
{
if(a.y == b.y)
return a.x < b.x;
return a.y < 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)
{
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 combine(int s, int d, double width)
{
double Min=width;
sort(v+s, v+d+1, by_y);
for(int i=s; i<=d; i++)
for(int j=i+1; j<=d && j<=i+7; j++)
Min = min(Min, dis(i, 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;
}