Pagini recente » Cod sursa (job #919116) | Cod sursa (job #3265497) | Cod sursa (job #525552) | Cod sursa (job #2534283) | Cod sursa (job #978973)
Cod sursa(job #978973)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
struct punct
{
int x,y;
} v[100005],ax;
int n1,n,i,p,s,i1;
double calc(int a,int b)
{
double dist;
double ax1,ax2;
ax1=v[a].x-v[b].x;
ax1=ax1*ax1;
ax2=v[a].y-v[b].y;
ax2=ax2*ax2;
dist=sqrt(ax1+ax2);
return dist;
}
double dei(int l, int r)
{
if (r-l==1)
{
double dist;
dist=calc(l,r);
return dist;
}
if (r-l==2)
{
double dist1,dist2,dist3;
dist1=calc(l,l+1);
dist2=calc(l,r);
dist3=calc(r-1,r);
return min(min(dist1,dist2),dist3);
}
double distl,distr,dist;
int mij;
mij=(l+r)/2;
distl=dei(l,mij);
distr=dei(mij+1,r);
dist=min(distl,distr);
int ll,rr;
ll=v[mij].x-dist;
rr=v[mij].x+dist;
while (v[l].x<ll)
l++;
while (v[r].x<rr)
r--;
int i,j;
for (i=l;i<r;i++)
for (j=i+1;((j<=r)||(j<=i+7));j++)
dist=min(dist,calc(i,j));
return dist;
}
int godown(int s)
{
if (2*s>n1)
return 0;
if (2*s+1<=n1)
{
if (max(v[s].x,max(v[s*2].x,v[s*2+1].x))==v[s].x)
return 0;
if (v[s*2].x>v[s*2+1].x)
return s*2;
return s*2+1;
}
if (max(v[s].x,v[s*2].x)==v[s].x)
return 0;
return s*2;
}
int main(void)
{
FILE * f;
f=fopen("cmap.in","r");
ofstream g("cmap.out");
fscanf(f,"%d",&n);
for (i=1;i<=n;i++)
{
fscanf(f,"%d%d",&v[i].x,&v[i].y);
p=i;
while ((p>1)&&(v[p/2].x<v[p].x))
{
ax=v[p];
v[p]=v[p/2];
v[p/2]=ax;
p=p/2;
}
}
n1=n;
for (i=1;i<=n;i++)
{
ax=v[n1];
v[n1]=v[1];
v[1]=ax;
n1--;
s=1;
p=godown(s);
while (p!=0)
{
ax=v[s];
v[s]=v[p];
v[p]=ax;
s=p;
p=godown(s);
}
}
g<<setiosflags(ios::fixed)<<setprecision(7)<<dei(1,n);
g.close();
return 0;
}