Pagini recente » Cod sursa (job #1769554) | Cod sursa (job #1140946) | Cod sursa (job #268464) | Cod sursa (job #1786044) | Cod sursa (job #1716165)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define x first
#define y second
#define mkp make_pair
#define ll long long
#define inf 900000000000000000
using namespace std;
ifstream si("cmap.in");
ofstream so("cmap.out");
pair<int,int> v[100005],aux[100005];
bool cmp(pair<int,int> a,pair<int,int> b)
{
if(a.y<b.y)
return true;
if(a.y==b.y)
if(a.x<b.x)
return true;
return false;
}
ll dist(pair<int,int> a,pair<int,int> b)
{
return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}
ll rezolva(int st,int dr)
{
if(st>=dr)
return inf;
if(st==dr-1)
{
if(cmp(v[dr],v[st]))
{
swap(v[st],v[dr]);
}
return dist(v[st],v[dr]);
}
int mid=(st+dr)/2,midx=v[mid].x;
ll sol=min(rezolva(st,mid),rezolva(mid+1,dr));
merge(v+st,v+mid+1,v+mid+1,v+dr+1,aux+1,cmp);
int i,j,nr=0;
for(i=1;i<=dr-st+1;i++)
v[st+i-1]=aux[i];
for(i=1;i<=dr-st+1;i++)
if(1LL*abs(aux[i].x-midx)*abs(aux[i].x-midx)<=sol)
aux[++nr]=aux[i];
for(i=1;i<=nr;i++)
for(j=i+1;j<=nr&&1LL*(aux[j].y-aux[i].y)*(aux[j].y-aux[i].y)<=sol;j++)
sol=min(sol,dist(aux[i],aux[j]));
return sol;
}
int main()
{
int n;
si>>n;
int i,a,b;
for(i=1;i<=n;i++)
{
si>>a>>b;
v[i]=mkp(a,b);
}
sort(v+1,v+1+n);
//for(i=1;i<=n;++i)
// cout<<v[i].x<<' '<<v[i].y<<'\n';
so<<sqrt(rezolva(1,n));
return 0;
}