Pagini recente » Cod sursa (job #1418251) | Cod sursa (job #368324) | Cod sursa (job #346846) | Cod sursa (job #1440250) | Cod sursa (job #2725916)
#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;
}