Pagini recente » Cod sursa (job #2539813) | Cod sursa (job #1262614) | Cod sursa (job #2683618) | Cod sursa (job #1702335) | Cod sursa (job #2303787)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct coord
{
int x,y;
};
coord t[100001],v[100001];
int i,j,m,n,x,y;
bool funct(coord a, coord b)
{
if (a.x>b.x) return 0;
if (b.x>a.x) return 1;
if (a.y>b.y) return 0;
return 1;
}
double dist(coord a, coord b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double ds(int a,int b)
{
double s;
if (b-a<3)
{
if (b-a==1) return dist(t[a],t[b]);
return min(dist(t[a],t[b]),min(dist(t[a],t[a+1]),dist(t[a+1],t[b])));
}
int mid=(a+b)/2,poz=0;
s=min(ds(a,mid),ds(mid,b));
for (i=a;i<=b;i++)
if (abs(t[i].x-t[mid].x)<s) v[++poz]=t[i];
for (int i=1;i<poz;i++)
for (j=i+1;j<=poz && j-i<8;j++)
if (dist(v[i],v[j])<s) s=dist(v[i],v[j]);
return s;
// practic rezolvat, tu deam fa tabelu v de la a la b parcurgand si vazand ca distanta
// dsa fie mai mica ca s si adauga in v, apoi compara
}
int main()
{
fin>>n;
for (i=1;i<=n;i++)
fin>>t[i].x>>t[i].y;
sort(t+1,t+n+1,funct);
//for (i=1;i<=n;i++)
// fout<<t[i].x<<" "<<t[i].y<<"\n";
fout<<fixed<<setprecision(6)<<ds(1,n);
return 0;
}