Cod sursa(job #615110)

Utilizator vladbagrinVlad Bagrin vladbagrin Data 8 octombrie 2011 16:47:21
Problema Cele mai apropiate puncte din plan Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 2.44 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

#define mymin(x, y) x <= y ? x : y
#define minimize(minim, candidate) if (candidate < minim) minim = candidate

typedef struct coord {
	int 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));
}

void swap(coord* a, int i, int j) {
	coord t = a[i];
	a[i] = a[j];
	a[j] = t;
}

coord y[MAX], yfull[MAX];
double find_min(coord* a, int l, int r) {
	double minim;
	int n = r - l + 1;
	if (n <= 3) {
		int i, j;
		minim = DBL_MAX;
		for (i = l; i <= r; i++) {
			for (j = i + 1; j <= r; j++) {
				double d = distance(a[i], a[j]);
				minimize(minim, d);
			}
		}
		//qsort(a + l, r - l + 1, sizeof(coord), compare_y);
		/*if (n > 1) {
			if (a[l].y > a[l + 1].y) {
				swap(a, l, l + 1);
			}
			if (n == 3) {
				if (a[l + 1].y > a[r].y) {
					swap(a, l + 1, r);
				}
				if (a[l].y > a[l + 1].y) {
					swap(a, l, l + 1);
				}
			}
		}*/
	} else {
		int m = (l + r) / 2;
		double delim = ((double) a[m].x + a[m + 1].x) / 2;
		double min_l = find_min(a, l, m), min_r = find_min(a, m + 1, r);
		minim =  mymin(min_l, min_r);

		int n = 0, k = 0, i = l, j = m + 1;
		while (i <= m && j <= r) {
			if (a[i].y < a[j].y) {
				yfull[n++] = a[i++];
			} else {
				yfull[n++] = a[j++];
			}
		}
		while (i <= m) {
			yfull[n++] = a[i++];
		}
		while (j <= r) {
			yfull[n++] = a[j++];
		}

		for (i = 0; i < n; i++) {
			if (fabs(yfull[i].x - delim) <= minim) {
				y[k++] = yfull[i];
			}
			a[l + i] = yfull[i];
		}

		for (i = 0; i < k; i++) {
			for (j = i + 1; j <= i + 7 && j < k; j++) {
				double d = distance(y[i], y[j]);
				minimize(minim, d);
			}
		}
	}
	return minim;
}

int main() {
	FILE *f = fopen(INPUT, "r");
	coord a[MAX];
	int n, i, res;
	res = fscanf(f, "%d", &n);
	for (i = 0; i < n; i++) {
		res = 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;
}