Pagini recente » Cod sursa (job #1869233) | Cod sursa (job #1157094) | Cod sursa (job #868662) | Cod sursa (job #2190683) | Cod sursa (job #2969528)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#define lr long double
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
const int N=1e5+3;
struct pct
{
int x,y;
}a[N];
int b[N];
bool comp(pct X,pct Y)
{
if(X.x==Y.x)
return X.y<Y.y;
return X.x<Y.x;
}
lr dist(pct X,pct Y)
{
return sqrt((X.x-Y.x)*(X.x-Y.x)+(X.y-Y.y)*(X.y-Y.y));
}
lr calc(int st,int dr)
{
if(dr-st+1<=3)
{
lr mn=1e12;
for(int i=st;i<=dr;i++)
for(int j=i+1;j<=dr;j++)
mn=min(mn,dist(a[i],a[j]));
for(int i=st;i<=dr;i++)
for(int j=i+1;j<=dr;j++)
if(a[i].y>a[j].y)
swap(a[i],a[j]);
return mn;
}
else
{
int mj=(st+dr)/2;
lr as=a[mj].x;
lr dst=calc(st,mj);
lr ddr=calc(mj+1,dr);
lr dmin=min(dst,ddr);
vector<pct>b;
vector<pct>c;
for(int i=st;i<=mj;i++)
if(abs(a[i].x-as)<=dmin)
b.push_back(a[i]);
int s1=b.size()-1;
for(int i=mj+1;i<=dr;i++)
if(abs(a[i].x-as)<=dmin)
b.push_back(a[i]);
int p1=0;
int p2=s1+1;
int s2=b.size()-1;
while(p1<=s1&&p2<=s2)
{
if(abs(b[p1].x-as)<=abs(b[p2].x-as))
c.push_back(b[p1]),p1++;
else
c.push_back(b[p2]),p2++;
}
while(p1<=s1)
c.push_back(b[p1]),p1++;
while(p2<=s2)
c.push_back(b[p2]),p2++;
for(int i=0;i<c.size();i++)
for(int w=1;w<=7&&w+i<c.size();w++)
dmin=min(dmin,dist(c[i],c[i+w]));
b.clear();
p1=st;
p2=mj+1;
while(p1<=mj&&p2<=dr)
{
if(a[p1].y<a[p2].y)
b.push_back(a[p1]),p1++;
else
b.push_back(a[p2]),p2++;
}
while(p1<=mj)
b.push_back(a[p1]),p1++;
while(p2<=dr)
b.push_back(a[p2]),p2++;
for(int i=st;i<=dr;i++)
a[i]=b[i-st];
return dmin;
}
}
int main()
{
f>>n;
for(int i=1;i<=n;i++)
f>>a[i].x>>a[i].y;
sort(a+1,a+n+1,comp);
g<<fixed<<setprecision(8)<<calc(1,n);
return 0;
}