Cod sursa(job #2889514)

Utilizator PodeliPodeanu Matei Alexandru Podeli Data 12 aprilie 2022 20:57:19
Problema Cele mai apropiate puncte din plan Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.94 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include <stdbool.h>
typedef struct{
    int x,y;
}Point;
void merge(Point *P,int st,int mij,int dr,bool s){
    int n1=mij-st+1;
    int n2=dr-mij;
    Point *a=malloc(n1*sizeof(Point));
    Point *b=malloc(n2*sizeof(Point));
    for(int i=0;i<n1;i++)
        a[i]=P[st+i];
    for(int j=0;j<n2;j++)
        b[j]=P[mij+1+j];
    int i=0,j=0,k=st;
    while(i<n1&&j<n2){
        if(s) {
            if (a[i].x < b[j].x) {
                P[k] = a[i];
                i++;
            } else {
                P[k] = b[j];
                j++;
            }
            k++;
        }
        else {
            if (a[i].y < b[j].y) {
                P[k] = a[i];
                i++;
            } else {
                P[k] = b[j];
                j++;
            }
            k++;
        }
    }
    while (i < n1) {
        P[k] = a[i];
        i++;
        k++;
    }
    while (j < n2) {
        P[k] = b[j];
        j++;
        k++;
    }
    free(a);
    free(b);
}
void divsort(Point *P,int st,int dr,bool s){
    if(st<dr){
        int mij=(st+dr)/2;
        divsort(P,st,mij,s);
        divsort(P,mij+1,dr,s);
        merge(P,st,mij,dr,s);
    }
}
double dist(Point a,Point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double distmin(Point *P,int st,int dr){
    double min= dist(P[0],P[1]);
    for(int i=st;i<=dr;i++){
        for(int j=i+1;j<=dr;j++)
            if(dist(P[i],P[j])<min)
                min=dist(P[i],P[j]);
    }
    return min;
}
double min(double a,double b){
    if(a<b)
        return a;
    return b;
}
double stripCl(Point *strip,int n,double d){
    divsort(strip,0,n-1,0);
    //qsort(strip,n,sizeof(Point),cmpy);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n && (strip[j].y-strip[i].y)<d;j++)
            if(dist(strip[i],strip[j])<d)
                d=dist(strip[i],strip[j]);
    }
    return d;
}
double divide(Point *P,int st,int dr){
    if(dr-st<=2){
        return distmin(P,st,dr);
    }
    int mij=st+(dr-st)/2;
    double div1,div2,divmin;
    div1=divide(P,st,mij);
    div2=divide(P,mij+1,dr);
    divmin=min(div1,div2);
    Point vect[dr];
    int j=0;
    for(int i=0;i<dr;i++){
        if(abs(P[i].x-P[mij].x)<divmin){
            vect[j] = P[i];
            j++;}
    }
    return min(divmin,stripCl(vect,j,divmin));
}
int main()
{
    int n;
    FILE *fptr1,*fptr2;

    // use appropriate location if you are using MacOS or Linux
    fptr1 = fopen("cmap.in","r");
    fptr2 = fopen("cmap.out","w");
    if(fptr1 == NULL)
    {
        printf("Error!");
        exit(1);
    }
    fscanf(fptr1,"%d",&n);
    //printf("%d\n",n);
    Point *P=(Point *)malloc(n*sizeof(Point));
    for(int i=0;i<n;i++){
        fscanf(fptr1,"%d %d",&P[i].x,&P[i].y);
    }
    //for(int i=0;i<n;i++){
    //    printf("%d %d\n",P[i].x,P[i].y);
    //}
    divsort(P,0,n-1,true);
    fprintf(fptr2,"%lf\n",divide(P,0,n-1));
    free(P);
    fclose(fptr1);
    fclose(fptr2);
    return 0;
}