Cod sursa(job #614601)

Utilizator vladbagrinVlad Bagrin vladbagrin Data 6 octombrie 2011 21:45:06
Problema Cele mai apropiate puncte din plan Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>

#define INPUT "cmap.in"
#define OUTPUT "cmap.out"
#define MAX 100000
#define SUCCESS 0

typedef struct coord {
	long x, y;
} coord;

int compare_y(const void* a, const void* b) {
	int ya = ((coord*) a)->y, yb = ((coord*) b)->y;
	if (ya == yb) {
		return 0;
	} else {
		return ya < yb ? -1 : 1;
	}
}

int compare_x(const void* a, const void* b) {
	int xa = ((coord*) a)->x, xb = ((coord*) b)->x;
	if (xa == xb) {
		return compare_y(a, b);
	} else {
		return xa < xb ? -1 : 1;
	}
}

double distance(coord a, coord b) {
	return sqrt(pow((double) a.x - b.x, 2) + pow((double) a.y - b.y, 2));
}

coord y[MAX];
double find_min(coord* a, int l, int r) {
	double minim;
	if (r - l + 1 <= 3) {
		int i;
		minim = DBL_MAX;
		while (l <= r) {
			for (i = l + 1; i <= r; i++) {
				minim = fmin(minim, distance(a[l], a[i]));
			}
			l++;
		}
	} else {
		int m = (l + r) / 2;
		double delim = ((double) a[m].x + a[m + 1].x) / 2;
		minim =  fmin(find_min(a, l, m), find_min(a, m + 1, r));

		int n = 0, i, j;
		for (; l <= r; l++) {
			if (fabs(a[l].x - delim) <= minim) {
				y[n++] = a[l];
			}
		}
		qsort(y, n, sizeof(coord), compare_y);
		for (i = 0; i < n; i++) {
			for (j = i + 1; j <= i + 7 && j < n; j++) {
				minim = fmin(minim, distance(y[i], y[j]));
			}
		}
	}
	return minim;
}

int main() {
	FILE *f = fopen(INPUT, "r");
	coord a[MAX];
	long n, i;
	fscanf(f, "%d", &n);
	for (i = 0; i < n; i++) {
		fscanf(f, "%d %d", &a[i].x, &a[i].y);
	}
	fclose(f);

	qsort(a, n, sizeof(coord), compare_x);

	f = fopen(OUTPUT, "w");
	fprintf(f, "%f\n", find_min(a, 0, n - 1));
	fclose(f);
	return SUCCESS;
}