Cod sursa(job #1662840)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 25 martie 2016 10:11:32
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#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;
}