Pagini recente » Cod sursa (job #2840854) | Cod sursa (job #862744) | Cod sursa (job #1816922) | Cod sursa (job #174171) | Cod sursa (job #2618405)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
typedef pair<int,int> p;
p v[100005];
long double dist(p a,p b)
{
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
long double divide(int a, int b)
{
long double Min = INT_MAX*1.0;
if(b-a+1<=3)
{
for(int i=a;i<=b;i++)
{
for(int j=i+1;j<=b;j++)
{
if(dist(v[i],v[j])<Min)
{
Min=dist(v[i],v[j]);
}
}
}
return Min;
}
int mij=(a+b)/2;
Min=min(divide(a,mij),divide(mij+1,b));
vector <p> points;
for(int i=a;i<=b;i++)
{
if(abs(v[i].x-v[mij].x)<=Min && abs(v[i].y-v[mij].y)<=Min)
{
points.push_back(v[i]);
}
}
for(int i=a;i<=b;i++)
{
for(int j=i+1;j<=i+7;j++)
{
Min=min(Min,dist(v[i],v[j]));
}
}
return Min;
}
int main()
{
f>>n;
for(int i=1;i<=n;i++)
{
f>>v[i].first>>v[i].second;
}
sort(v+1,v+n+1);
g<<fixed<<setprecision(6);
g<<divide(1,n)<<'\n';
return 0;
}