Pagini recente » Istoria paginii runda/feofjeofnqefe | Cod sursa (job #1877690) | Cod sursa (job #963480) | Cod sursa (job #1913869) | Cod sursa (job #1662840)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define lim 100005
#define infin 2000000000
using namespace std;
struct elem{int x,y;};
elem v[lim],aux[lim];
bool cmp(elem a,elem b){
return a.x < b.x;
}
void interclas(int st,int mij,int dr){
int i=st,j=mij+1,k=st;
while(i<=mij&&j<=dr){
if(v[i].y<=v[j].y){
aux[k++]=v[i];
i++;
}
else{
aux[k++]=v[j];
j++;
}
}
while(i<=mij){
aux[k++]=v[i];
i++;
}
while(j<=dr){
aux[k++]=v[j];
j++;
}
for(i=st;i<=dr;i++)
v[i]=aux[i];
}
double dist(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double divtimp(int st,int dr){
int mij,med,i,j,k;
double rasp,delta;
if(st==dr)
return infin;
mij=(st+dr)/2;
med=v[mij].x;
delta=divtimp(st,mij);
rasp=divtimp(mij+1,dr);
if(rasp<delta)
delta=rasp;
i=st;
j=mij+1;
interclas(st,mij,dr);
k=0;
for(i=st;i<=dr;i++)
if(v[i].x>=med-delta&&v[i].x<=med+delta){
k++;
aux[k]=v[i];
}
for(i=1;i+7<=k;i++)
for(j=1;j<=7;j++){
rasp=dist(aux[i].x,aux[i].y,aux[i+j].x,aux[i+j].y);
if(rasp<delta)
delta=rasp;
}
return delta;
}
int main(){
FILE *fin,*fout;
fin=fopen("cmap.in","r");
fout=fopen("cmap.out","w");
int i,n;
double rasp;
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++)
fscanf(fin,"%d%d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
rasp=divtimp(1,n);
fprintf(fout,"%0.6f",rasp);
fclose(fin);
fclose(fout);
return 0;
}