Cod sursa(job #2756156)

Utilizator MaxamPJORares Daniel MaxamPJO Data 29 mai 2021 23:59:12
Problema Cele mai apropiate puncte din plan Scor 45
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.61 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
int x, y;
} coordonate;
coordonate *plan, *aux;
int n;
void swap(coordonate *a, coordonate *b){
coordonate aux=*a;
*a=*b;
*b=aux;
}
int pozfinx(int low, int high){
int j=low-1;
for(int i=low; i<high; i++){
    if(plan[i].x<=plan[high].x){
        j++;
        swap(plan+i, plan+j);
    }
}
j++;
swap(plan+j, plan+high);
return j;
}

int pozfiny(int low, int high){
int j=low-1;
for(int i=low; i<high; i++){
    if(aux[i].y<=aux[high].y){
        j++;
        swap(aux+i, aux+j);
    }
}
j++;
swap(plan+j, plan+high);
return j;
}

void quicksort(int low, int high, int (*tpf)(int low, int high)){
if(high>low){

    int poz=(*tpf)(low, high);
    quicksort(low, poz-1, tpf);
    quicksort(poz+1, high, tpf);
}
}

double distanta(coordonate a, coordonate b){
double pitagora=pow((a.x-b.x), 2)+pow((a.y-b.y), 2);
return sqrt(pitagora);
}
double minim(double a, double b){
if(a<b) return a;
return b;
}

double distantaminima(int low, int high){
double dmin=INFINITY, dactual;
if(high-low+1==3){
    dactual=distanta(plan[low], plan[low+2]);
    if(dactual<dmin){
        dmin=dactual;
    }
    dactual=distanta(plan[low+1], plan[low+2]);
    if(dactual<dmin){
        dmin=dactual;
    }
    dactual=distanta(plan[low], plan[low+1]);
    if(dactual<dmin){
        dmin=dactual;
    }
    return dmin;
}
if(high-low+1==2){
    dactual=distanta(plan[low], plan[low+1]);
    if(dactual<dmin){
        dmin=dactual;
    }
    return dmin;
}
if(!(high-low)) return dmin;

double de, dv;
int mid=(low+high)/2;
de=distantaminima(low, mid);
dv=distantaminima(mid+1, high);

dmin=minim(de, dv);
int l, h;
l=mid;
while(l>=low&&(plan[mid].x-plan[l].x)<dmin){
    aux[l]=plan[l];
    l--;
}
l++;
h=mid+1;
while(h<=high&&(plan[h].x-plan[mid+1].x)<dmin){
    aux[h]=plan[h];
    h++;
}
h--;
double d=dmin;
quicksort(l, h, pozfiny);

for(int i=l; i<=h; i++){
    int j=i+1;
    while(j<=h&&(plan[j].y-plan[i].y)<d){
    dactual=distanta(plan[i], plan[j]);
    if(dactual<dmin){
        dmin=dactual;
    }
    j++;
   }
}
return dmin;
}

int main()
{
    FILE *pf=fopen("cmap.in", "r");
    fscanf(pf, "%d", &n);
    plan=calloc(n, sizeof(coordonate));
    aux=calloc(n, sizeof(coordonate));
    int u, w;
    for(int i=0; i<n; i++){
    fscanf(pf, "%d %d", &u, &w);
    plan[i].x=u;
    plan[i].y=w;
    }
    fclose(pf);
    quicksort(0, n-1, pozfinx);
    double d=distantaminima(0, n-1);
    pf=fopen("cmap.out", "w");
    fprintf(pf, "%lf", d);
    fclose(pf);
    return 0;
}