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

typedef struct point_2d_s {
	int x;
	int y;
} point_2d_t;

point_2d_t *read_points(char *filename, int *n)
{
	FILE *f = fopen(filename, "r");
	if (!f) {
		printf("fopen: no such file '%s'!\n", filename);
		exit(1);
	}

	fscanf(f, "%d", n);

	point_2d_t *points = malloc(*n * sizeof(point_2d_t));
	if (!points) {
		printf("malloc: insufficient memory!\n");
		exit(1);
	}

	int i;
	for (i = 0; i < *n; i++)
		fscanf(f, "%d %d", &points[i].x, &points[i].y);

	fclose(f);
	return points;
}

void print_points(point_2d_t *points, int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d %d\n", points[i].x, points[i].y);
	printf("\n");

}

point_2d_t *copy_points(point_2d_t *points, int n)
{
	point_2d_t *points_copy = malloc(n * sizeof(point_2d_t));

	int i;
	for (i = 0; i < n; i++) {
		points_copy[i].x = points[i].x;
		points_copy[i].y = points[i].y;
	}

	return points_copy;
}

int compare_x(point_2d_t *a, point_2d_t *b)
{
	if (a->x == b->x)
		return 0;
	if (a->x < b->x)
		return -1;
	if (a->x > b->x)
		return 1;
}

int compare_y(point_2d_t *a, point_2d_t *b)
{
	if (a->y == b->y)
		return 0;
	if (a->y < b->y)
		return -1;
	if (a->y > b->y)
		return 1;
}

void merge_points(point_2d_t *points, int l, int m, int r, int (*compare_fct)(point_2d_t *, point_2d_t *))
{
	int i = l, j = m + 1, k = 0;
	point_2d_t *sorted_points = malloc((r - l + 1) * sizeof(point_2d_t));

	while (i <= m && j <= r)
		if (compare_fct(&points[i], &points[j]) <= 0) {
			sorted_points[k].x = points[i].x;
			sorted_points[k].y = points[i].y;
			k++;
			i++;
		} else {
			sorted_points[k].x = points[j].x;
			sorted_points[k].y = points[j].y;
			k++;
			j++;
		}

	while (i <= m) {
		sorted_points[k].x = points[i].x;
		sorted_points[k].y = points[i].y;
		k++;
		i++;
	}
	while (j <= r) {
		sorted_points[k].x = points[j].x;
		sorted_points[k].y = points[j].y;
		k++;
		j++;
	}

	for (i = l, k = 0; i <= r; i++) {
		points[i].x = sorted_points[k].x;
		points[i].y = sorted_points[k].y;
		k++;
	}

	free(sorted_points);
}

void sort_points(point_2d_t *points, int l, int r, int (*compare_fct)(point_2d_t *, point_2d_t *))
{
	if (l < r) {
		int m = (l + r) / 2;

		sort_points(points, l, m, compare_fct);
		sort_points(points, m + 1, r, compare_fct);

		merge_points(points, l, m, r, compare_fct);
	}
}

int equal_points(point_2d_t *a, point_2d_t *b)
{
	if (a->x == b->x && a->y == b->y)
		return 1;
	return 0;
}

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


double closest_split_pair_dist(point_2d_t *points_x, point_2d_t *points_y, int n, int m, double delta)
{
	point_2d_t *y_set = malloc(n * sizeof(point_2d_t));

	int i, k;
	for (i = 0, k = 0; i < n; i++) {
		if (points_x[m].x - delta <= points_y[i].x && points_y[i].x <= points_x[m].x + delta) {
			y_set[k].x = points_y[i].x;
			y_set[k].y = points_y[i].y;
			k++;
		}
	}

	double min_dist = delta;
	for (i = 0; i < k - 1; i++) {
		int j, elements_to_compare = (7 < k - 1 - i) ? 7 : k - 1 - i;
		for (j = 1; j < elements_to_compare; j++) {
			double d = dist(&y_set[i], &y_set[i + j]);
			if (d < min_dist)
				min_dist = d;
		}
	}

	free(y_set);
	return min_dist;
}

double closest_pair_dist(point_2d_t *points_x, point_2d_t *points_y, int n, int l, int r)
{
	if (r - l > 2) {
		int m = (l + r) / 2;

		double min_dist_left = closest_pair_dist(points_x, points_y, n ,l, m);
		double min_dist_right = closest_pair_dist(points_x, points_y, n, m + 1, r);

		double delta = min_dist_left < min_dist_right ? min_dist_left : min_dist_right;
		double min_dist_split = closest_split_pair_dist(points_x, points_y, n, m, delta);

		return delta < min_dist_split ? delta : min_dist_split;
	} else if (r - l == 1) {
		return dist(&points_x[l], &points_x[r]);
	} else if (r - l == 2) {
		double d1 = dist(&points_x[l], &points_x[l + 1]);
		double d2 = dist(&points_x[l], &points_x[r]);
		double d3 = dist(&points_x[l + 1], &points_x[r]);

		double min_dist = d1 < d2 ? d1 : d2;
		return d3 < min_dist ? d3 : min_dist;
	}
}

int main(int argc, char **argv)
{
/*
	if (argc != 2) {
		printf("usage: ./closest_points_pair <input_file>\n");
		exit(1);
	}
*/
	int n;
	point_2d_t *points = read_points(/*argv[1]*/ "cmap.in", &n);
	point_2d_t *points_copy = copy_points(points, n);

	sort_points(points, 0, n - 1, compare_x);
	sort_points(points_copy, 0, n - 1, compare_y);

	double min_dist = closest_pair_dist(points, points_copy, n, 0, n - 1);

	free(points);
	free(points_copy);

	FILE *f = fopen("cmap.out", "w");
	fprintf(f, "%f\n", min_dist);
	fclose(f);

	return 0;
}