Cod sursa(job #1408433)

Utilizator vladrochianVlad Rochian vladrochian Data 30 martie 2015 00:48:10
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int kMaxN = 100005;
const int64_t kInf = 4e18;

int N;
struct Point {
	int x, y;
} p[kMaxN], aux[kMaxN];
int64_t ans = kInf;

bool LessX(const Point &p1, const Point &p2) {
	return p1.x < p2.x;
}
bool LessY(const Point &p1, const Point &p2) {
	return p1.y < p2.y;
}

int64_t Dist(const Point &p1, const Point &p2) {
	int dx = p1.x - p2.x;
	int dy = p1.y - p2.y;
	return 1LL * dx * dx + 1LL * dy * dy;
}

void Read() {
	freopen("cmap.in", "r", stdin);
	scanf("%d", &N);
	for (int i = 0; i < N; ++i)
		scanf("%d%d", &p[i].x, &p[i].y);
}

void Solve(int l, int r) {
	if (r - l == 1)
		return;
	if (r - l == 2) {
		if (p[l].y > p[l + 1].y)
			swap(p[l], p[l + 1]);
		ans = min(ans, Dist(p[l], p[l + 1]));
		return;
	}

	int m = (l + r) >> 1;
	int xsep = p[m].x;
	Solve(l, m);
	Solve(m, r);
	merge(p + l, p + m, p + m, p + r, aux, LessY);
	memcpy(p + l, aux, (r - l) * sizeof(Point));

	int nr = 0;
	for (int i = l; i < r; ++i)
		if (abs(p[i].x - xsep) < ans)
			aux[nr++] = p[i];

	for (int i = 0; i < nr - 1; ++i)
		for (int j = i + 1; j < min(nr, i + 8); ++j)
			ans = min(ans, Dist(aux[i], aux[j]));
}

void Print() {
	freopen("cmap.out", "w", stdout);
	printf("%.6f\n", sqrt(ans));
}

int main() {
	Read();
	sort(p, p + N, LessX);
	Solve(0, N);
	Print();
}