Cod sursa(job #2725916)

Utilizator trucker4lifeMoraru Radu-Andrei trucker4life Data 19 martie 2021 20:52:12
Problema Cele mai apropiate puncte din plan Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.6 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

typedef struct {
    int x, y;
} punct;

double calc_dist(punct *a, punct *b) {
    return sqrt(pow(a->x - b->x, 2) + pow(a->y - b->y, 2));
}

int compare_x(const void *a, const void *b);
int compare_y(const void *a, const void *b);

double calc_dist_min(int L, int R, punct *sort_x, punct *sort_y) {
    double dist_min;

    if (R-L < 4) {
        qsort(sort_y+L, R-L, sizeof*sort_y, compare_y);
        dist_min = calc_dist(sort_y+L, sort_y+L+1);

        for (int i = L; i < R; i++)
            for (int j = L; j < i; j++) {
                double d = calc_dist(sort_y+i, sort_y+j);
                if (d < dist_min) dist_min = d;
            }

        return dist_min;
    }

    int M = (L+R+1)/2;
    double dL = calc_dist_min(L, M, sort_x, sort_y);
    double dR = calc_dist_min(M, R, sort_x, sort_y);

    dist_min = dL;
    if (dR < dL)    dist_min = dR;

    punct *valid = malloc((R-L) * sizeof *valid);
    int iter = 0;
    for (int i = L; i < R; i++) {
        if (sort_y[i].x >= sort_x[M].x - dist_min &&
            sort_y[i].x <= sort_x[M].x + dist_min) {

            valid[iter++] = sort_y[i];
        }
    }

    for (int i = 0; i < iter; i++) {
        for (int j = i-1; j >= 0 && i-j<=8; j--) {
            double temp_dist = calc_dist(valid+i, valid+j);
            if (temp_dist < dist_min)
                dist_min = temp_dist;
        }
    }

    free(valid);
    qsort(sort_y+L, R-L, sizeof*sort_y, compare_y);
    return dist_min;
}

int main() {
    FILE *fin = fopen("cmap.in", "r");
    FILE *fout = fopen("cmap.out", "w");

    int n;
    double dist_min;

    fscanf(fin, "%d", &n);

    punct *sort_x = malloc(n * sizeof*sort_x);
    punct *sort_y = malloc(n * sizeof*sort_y);

    for (int i = 0; i < n; i++) {
        fscanf(fin, "%d %d", &(sort_x+i)->x, &(sort_x+i)->y);
    }

    qsort(sort_x, n, sizeof *sort_x, compare_x);
    for (int i = 0; i < n; i++) {
        sort_y[i] = sort_x[i];
    }

    dist_min = calc_dist_min(0, n, sort_x, sort_y);

    free(sort_x);
    free(sort_y);

    fprintf(fout, "%.7f", dist_min);

    fclose(fin);
    fclose(fout);
}

int compare_y(const void *a, const void *b) {
    punct *p1 = (punct *)a;
    punct *p2 = (punct *)b;

    if (p1->y > p2->y) return 1;
    else if (p1->y == p2->y) {
        return 0;
    }
    return -1;
}

int compare_x(const void *a, const void *b) {
    punct *p1 = (punct *)a;
    punct *p2 = (punct *)b;

    if (p1->x > p2->x) return 1;
    else if (p1->x == p2->x) {
        if (p1->y > p2->y) return 1;
        else if (p1->y == p2->y) return 0;
        return -1;
    }
    return -1;
}