Pagini recente » Cod sursa (job #2821262) | Cod sursa (job #2708546) | Cod sursa (job #2891167) | Cod sursa (job #552573) | Cod sursa (job #2567781)
#include <bits/stdc++.h>
#define PLL pair<long long,long long>
#define X first
#define Y second
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
PLL pct[100001],cpy[100001];
long long Z;
long long dist(PLL a,PLL b)
{
return (b.X-a.X)*(b.X-a.X)+(b.Y-a.Y)*(b.Y-a.Y);
}
void Find(int st,int dr)
{
if(dr<=st)
return;
if(st+1==dr)
{
if(pct[st].Y>pct[dr].Y)
swap(pct[st],pct[dr]);
Z=min(Z,dist(pct[st],pct[dr]));
return;
}
int mid=(st+dr)/2;
Find(st,mid);Find(mid+1,dr);
int p1=st,p2=mid+1;
int poz=st;
while(p1<=mid && p2<=dr)
if(pct[p1].Y<=pct[p2].Y)
cpy[poz++]=pct[p1++];
else
cpy[poz++]=pct[p2++];
while(p1<=mid)
cpy[poz++]=pct[p1++];
while(p2<=dr)
cpy[poz++]=pct[p2++];
for(int i=st;i<=dr;i++)
pct[i]=cpy[i];
for(int i=st;i<=dr;i++)
for(int j=i+1;j<=min(i+8,dr);j++)
Z=min(Z,dist(pct[i],pct[j]));
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
in>>pct[i].X>>pct[i].Y;
sort(pct+1,pct+1+n);
Z=dist(pct[1],pct[2]);
Find(1,n);
out<<setprecision(6)<<fixed<<sqrt(Z);
return 0;
}