Pagini recente » Cod sursa (job #1134688) | Cod sursa (job #1369019) | Cod sursa (job #2280961) | Cod sursa (job #3127949) | Cod sursa (job #1334626)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define ll long long
#define inf 1LL<<63-3
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct pct
{ int x,y; } p[100005],ps[100005],v[100005],m[100005];
bool comp1(pct a,pct b)
{ if (a.x<b.x) return 1;
if (a.x>b.x) return 0;
return a.y<b.y;
}
bool comp2(pct a,pct b)
{ if (a.y<b.y) return 1;
if (a.y>b.y) return 0;
return a.x<b.x;
}
ll Dist(pct i,pct j)
{ return 1LL*(i.x-j.x)*(i.x-j.x)+1LL*(i.y-j.y)*(i.y-j.y); }
int n,k,km;
void Merge(int st,int dr)
{ int i,mid=(st+dr)/2,i1,i2;
km=0; i1=st; i2=mid+1;
while(i1<=mid && i2<=dr)
{
if (comp2(ps[i1],ps[i2])) {km++; m[km]=ps[i1]; i1++;}
else {km++; m[km]=ps[i2]; i2++;}
}
if (i1<=mid)
for(;i1<=mid;i1++)
{km++; m[km]=ps[i1];}
if (i2<=dr)
for(;i2<=dr;i2++)
{km++; m[km]=ps[i2];}
for(i=1;i<=km;i++)
ps[i+st-1]=m[i];
}
ll Closest(int st,int dr)
{ ll res=inf,res1,res2; int i,j,mid=(st+dr)/2,ind=p[mid].x;
if (dr-st+1<=3)
{
for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
{res1=(ll)Dist(p[i],p[j]);
if (res1<res) res=res1;
}
sort(ps+st,ps+dr+1,comp2);
return res;
}
res1=(ll)Closest(st,mid);
res2=(ll)Closest(mid+1,dr);
if (res1<res2) res=res1; else res=res2;
Merge(st,dr);
k=0;
for(i=st;i<=dr;i++)
if (ps[i].x>=ind-res && ps[i].x<=ind+res)
{k++; v[k].x=ps[i].x; v[k].y=ps[i].y;}
for(i=1;i<=k;i++)
for(j=i+1;j<=i+7 && j<=k;j++)
res=min(res,Dist(v[i],v[j]));
return (ll)res;
}
int main()
{ int i,j; ll res=inf;
f>>n;
for(i=1;i<=n;i++)
f>>p[i].x>>p[i].y;
sort(p+1,p+n+1,comp1);
for(i=1;i<=n;i++)
{ ps[i].x=p[i].x;
ps[i].y=p[i].y;
}
g<<fixed<<setprecision(8)<<sqrt((ll)Closest(1,n))<<"\n";
return 0;
}