// Savin Cristina-Diana
// Grupa 164
// Problema 8
// Tema Divide et Impera

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include <assert.h>

#define EPS 0.000001
#define test1 "/Users/cristinasavin/CLionProjects/untitled1/test1.txt"
#define test2 "/Users/cristinasavin/CLionProjects/untitled1/test2.txt"
#define test3 "/Users/cristinasavin/CLionProjects/untitled1/test3.txt"
#define test4 "/Users/cristinasavin/CLionProjects/untitled1/test4.txt"
#define test5 "/Users/cristinasavin/CLionProjects/untitled1/test5.txt"
#define test6 "/Users/cristinasavin/CLionProjects/untitled1/test6.txt"
#define test7 "/Users/cristinasavin/CLionProjects/untitled1/test7.txt"
#define test8 "/Users/cristinasavin/CLionProjects/untitled1/test8.txt"
#define test9 "/Users/cristinasavin/CLionProjects/untitled1/test9.txt"
#define test10 "/Users/cristinasavin/CLionProjects/untitled1/test10.txt"
#define ok1 "/Users/cristinasavin/CLionProjects/untitled1/ok1.txt"
#define ok2 "/Users/cristinasavin/CLionProjects/untitled1/ok2.txt"
#define ok3 "/Users/cristinasavin/CLionProjects/untitled1/ok3.txt"
#define ok4 "/Users/cristinasavin/CLionProjects/untitled1/ok4.txt"
#define ok5 "/Users/cristinasavin/CLionProjects/untitled1/ok5.txt"
#define ok6 "/Users/cristinasavin/CLionProjects/untitled1/ok6.txt"
#define ok7 "/Users/cristinasavin/CLionProjects/untitled1/ok7.txt"
#define ok8 "/Users/cristinasavin/CLionProjects/untitled1/ok8.txt"
#define ok9 "/Users/cristinasavin/CLionProjects/untitled1/ok9.txt"
#define ok10 "/Users/cristinasavin/CLionProjects/untitled1/ok10.txt"


typedef struct Punct{
    long int x;
    long int y;
}Punct;

int compare_x(const void *a, const void *b) {

    Punct *punctA = (Punct *)a;
    Punct *punctB = (Punct *)b;

    return (int)(punctA->x - punctB->x);
}

int compare_y(const void *a, const void *b) {

    Punct *punctA = (Punct *)a;
    Punct *punctB = (Punct *)b;

    return (int)(punctA->y - punctB->y);
}

double distanta(Punct p1, Punct p2)
{
    // Aceasta functie calculeaza distanta dintre doua puncte p1 si p2.
    return sqrt((double)((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y)));
}

double minim(double x, double y)
{
    return (x<y) ? x:y;
}

double modul(float x)
{
    return (x>0) ? x:-x;
}

double minimul_dintre_submultimi(Punct *p, int st, int dr, double d_min)
{
    // Aceasta functie calculeaza distanta minima dintre doua puncte in cazul in care unul apartine unei
    // submultimi, iar celalalt celeilalteia.

    int mij = (st + dr)/2;
    float dreapta = (float)(p[mij].x + p[mij+1].x) / 2;

    // Daca unul dintre punctele din mijloc, p[mij] sau p[mij+1], se afla la o distanta fata de dreapta
    // care imparte cele doua submultimi mai mare decat distanta minima d_min, atunci nu este necesar calculul
    // distantei minime dintre punctele cu proprietatea ca unul apartine unei submultimi si celalalt celeilalteia
    // deoarece aceasta distanta va fi mai mare decat distanta minima d_min.

    if(modul(dreapta - (float)p[mij].x) > d_min || modul((float)p[mij + 1].x - dreapta) > d_min)
        return DBL_MAX;

    // Construirea sirului y (sirul ce contine puncte din ambele submultimi)

    Punct *y = (Punct *)malloc(2 * sizeof(Punct));
    if(y == NULL){
        puts("Eroare la alocarea dinamica");
        exit(1);
    }

    int k = 0;

    y[k++] = p[mij];
    y[k++] = p[mij + 1];

    // Adaugam punctele ce se afla inaintea lui p[mij] pe axa Ox

    if(st <= mij-1 && mij-1 <= dr){
        int i = mij-1;
        while(modul(dreapta - (float)p[i].x) < d_min){
            y = realloc(y, (k + 1) * sizeof(Punct));
            if(y == NULL){
                puts("Eroare la alocarea dinamica");
                exit(1);
            }
            y[k++] = p[i--];

            if(st > i || i > dr)
                break;
        }
    }

    // Adaugam punctele ce se afla dupa p[mij+1] pe axa Ox

    if(st <= mij+2 && mij+2 <= dr) {
        int j = mij+2;
        while (modul((float) p[j].x - dreapta) < d_min) {
            y = realloc(y, (k + 1) * sizeof(Punct));
            if(y == NULL){
                puts("Eroare la alocarea dinamica");
                exit(1);
            }
            y[k++] = p[j++];

            if (st > j || j > dr)
                break;
        }
    }

    // Sortam sirul y in functie de y (axa Oy)

    qsort(y, k, sizeof(Punct), compare_y);

    // Calculam minimul din sirul y (sunt considerate doar primele 7 puncte),
    // conform explicatiei (https://www.infoarena.ro/problema/cmap)

    int a, b;
    for(a = 0; a < k-1; a++)
        for(b = a+1; b <= a+7 && b < k; b++)
            if(a != b && distanta(y[a], y[b]) < d_min)
                d_min = distanta(y[a], y[b]);

    free(y);

    return d_min;
}

double distanta_minima(Punct *p, int st, int dr)
{
    // Aceasta functie foloseste metoda divide et impera pentru
    // a calcula distanta minima din p.

    if(dr - st > 2){
        // Divide et impera

        int mij = (st + dr)/2;
        double d1, d2, d3;

        d1 = distanta_minima(p, st, mij);
        d2 = distanta_minima(p, mij+1, dr);

        // d3 reprezinta distanta minima dintre punctele cu proprietatea ca
        // unul apartine primei submultimi (st, mij), iar celalalt apartine
        // celelaltei submultimi (mij+1, dr)
        d3 = minimul_dintre_submultimi(p, st, dr, minim(d1, d2));

        return minim(minim(d1, d2), d3);
    }

    // In calzul in care numarul elementelor este mai mic sau egal cu 3,
    // calculam distanta minima.

    int i, j;
    double d_min = DBL_MAX;
    for(i = st; i <= dr-1; i++)
        for(j = st+1; j <=dr; j++)
            if(i != j && distanta(p[i], p[j]) < d_min)
                d_min = distanta(p[i], p[j]);
    return d_min;
}

double rezultat_calculat(char *fname)
{
    FILE *fin;
    fin = fopen(fname, "r");
    if(fin == NULL){
        puts("Eroare la deschiderea fisierului");
        exit(1);
    }
    int n, i;
    fscanf(fin, "%d", &n);

    // Crearea si citirea vectorului p (ce contine cele n puncte)

    Punct *p = (Punct *)malloc(n * sizeof(Punct));
    if(p == NULL){
        puts("Eroare la alocarea dinamica");
        exit(1);
    }
    for (i = 0; i < n; i++){
        fscanf(fin, "%ld", &p[i].x);
        fscanf(fin, "%ld", &p[i].y);
    }

    // Sortarea vectorului p in functie de x

    qsort(p, n, sizeof(Punct), compare_x);

    // Distanta minima

    double r = distanta_minima(p, 0, n - 1);

    free(p);
    fclose(fin);

    return r;
}

double rezultat_corect(char *fname)
{
    // Aceasta functie extrage rezultatul corect din fisierele
    // folosite pentru testarea programului.

    FILE *fout;
    fout = fopen(fname, "r");
    if(fout == NULL){
        puts("Eroare la deschiderea fisierului");
        exit(1);
    }
    double rezultat;
    fscanf(fout, "%lf", &rezultat);
    fclose(fout);
    return rezultat;
}

int main()
{
    assert(modul(rezultat_calculat(test1) - rezultat_corect(ok1)) < EPS);
    assert(modul(rezultat_calculat(test2) - rezultat_corect(ok2)) < EPS);
    assert(modul(rezultat_calculat(test3) - rezultat_corect(ok3)) < EPS);
    assert(modul(rezultat_calculat(test4) - rezultat_corect(ok4)) < EPS);
    assert(modul(rezultat_calculat(test5) - rezultat_corect(ok5)) < EPS);
    assert(modul(rezultat_calculat(test6) - rezultat_corect(ok6)) < EPS);
    assert(modul(rezultat_calculat(test7) - rezultat_corect(ok7)) < EPS);
    assert(modul(rezultat_calculat(test8) - rezultat_corect(ok8)) < EPS);
    assert(modul(rezultat_calculat(test9) - rezultat_corect(ok9)) < EPS);
    assert(modul(rezultat_calculat(test10) - rezultat_corect(ok10)) < EPS);

    puts("SUCCES");

    return 0;
}