Pagini recente » Cod sursa (job #2498644) | Cod sursa (job #2822702) | Cod sursa (job #2344960) | Cod sursa (job #1112613) | Cod sursa (job #2567748)
#include <bits/stdc++.h>
#define PLL pair<long double,long double>
#define X first
#define Y second
#define Inf 200000000000000000
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
PLL pct[100001],cpy[100001];
long long Z=Inf;
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(dr-st+1==2)
{
if(pct[st].Y>pct[st].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)
{
while(p1<=mid && pct[p1].Y<=pct[p2].Y)
cpy[poz++]=pct[p1++];
if(p1<=mid)
while(p2<=dr && pct[p2].Y<=pct[p1].Y)
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++)
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);
Find(1,n);
out<<setprecision(6)<<fixed<<sqrt(Z);
return 0;
}