Cod sursa(job #3292340)

Utilizator r0b3rtUngureanu Robert Anton r0b3rt Data 7 aprilie 2025 23:14:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define min(a,b) ((a) < (b) ? (a) : (b))

struct punct
{
    double ord;
    double abs;
};

int compare_ord(const void *A, const void *B)
{
    struct punct a=*((struct punct*)A);
    struct punct b=*((struct punct*)B);
    return (a.ord-b.ord);
}

int compare_abs(const void *A, const void *B)
{
    struct punct a=*((struct punct*)A);
    struct punct b=*((struct punct*)B);
    return (a.abs-b.abs);
}

double distanta(struct punct a, struct punct b)
{
    return sqrt((a.ord-b.ord)*(a.ord-b.ord)+(a.abs-b.abs)*(a.abs-b.abs));
}

int search_stg(struct punct sir[], int i, int j, double d)
{
    int rez=i;
    while(i<=j)
    {
        int m=i+(j-i)/2;
        if(sir[m].ord>=d)
        {
            j=m-1;
            rez=m;
        }
        else
            i=m+1;
    }
    return rez;
}

int search_dr(struct punct sir[], int i, int j, double d)
{
    int rez=j;
    while(i<=j)
    {
        int m=i+(j-i)/2;
        if(sir[m].ord<=d)
        {
            i=m+1;
            rez=m;
        }
        else
            j=m-1;
    }
    return rez;
}

double di(struct punct sir[], int i, int j)
{
    if(j==i)
        return __INT_MAX__;
    if(j-i==1)
        return distanta(sir[i], sir[j]);

    int m=i+(j-i)/2;
    double d_st=di(sir, i, m), d_dr=di(sir, m+1, j);
    double d=min(d_st, d_dr);

    int st=search_stg(sir, i, m, sir[m].ord-d);
    int dr=search_dr(sir, m+1, j, sir[m].ord+d);

    qsort((sir+st), (dr-st+1), sizeof(struct punct), compare_abs);

    for(int k=st; k<dr; k++)
    {
        for(int l=k+1; l<=dr && l<=k+6; l++)
            d=min(distanta(sir[k], sir[l]),d);
    }

    return d;
}

int main()
{
    FILE* in=fopen("cmap.in", "r"), *out=fopen("cmap.out" ,"w");
    int n;
    fscanf(in, "%d", &n);
    struct punct *sir=malloc(n*sizeof(struct punct));
    for(int i=0; i<n; i++)
    {
        fscanf(in, "%lf %lf", &sir[i].ord, &sir[i].abs);
    }
    qsort(sir, n, sizeof(struct punct), compare_ord);
    double rez=di(sir, 0, n-1);
    fprintf(out, "%lf", rez);
    return 0;
}