Pagini recente » Cod sursa (job #1020228) | Cod sursa (job #2772800) | Cod sursa (job #2629123) | Cod sursa (job #77824) | Cod sursa (job #1969724)
#include <bits/stdc++.h>
#define ll long long
#define Nmax 100005
#define INF 4e18
#define x first
#define y second
#define tip pair<ll,ll>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
vector< tip > v(Nmax);
vector< tip > v1;
vector< tip > v2;
ll get_dist(tip a, tip b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
ll rez(int p, int q, vector< tip > A, vector< tip > B)
{
if(p>=q-1)
return INF;
else if(q-p==2)
{
if(B[p]>B[p+1])
swap(B[p],B[p+1]);
return get_dist(A[p],A[p+1]);
}
int m=(p+q)/2;
ll best=min(rez(p,m,A,B),rez(m,q,A,B));
merge(B.begin()+p,B.begin()+m,B.begin()+m,B.begin()+q,v.begin());
copy(v.begin(),v.begin()+(q-p),B.begin()+p);
int nr=-1;
for(int i=p;i<q;i++)
if(abs(B[i].y-A[m].x)<=best)
v[++nr]=B[i];
for(int i=0;i<nr;i++)
{
for(int j=i+1;j<nr+1 and j-i<8;j++)
if(get_dist(v[i],v[j])<best)
best=get_dist(v[i],v[j]);
}
return best;
}
int main()
{int n;
f>>n;
ll x1,y1;
for(int i=1;i<=n;i++)
{
f>>x1>>y1;
v1.push_back({x1,y1});
}
sort(v1.begin(),v1.end());
for(int i=0;i<v1.size();i++)
v2.push_back({v1[i].x,v1[i].y});
g<<fixed<<setprecision(6)<<sqrt(rez(1,n,v1,v2));
return 0;
}