Cod sursa(job #821973)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 22 noiembrie 2012 20:27:21
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

int n, x, y;
vector<pair<int, int> > A;

inline double dis(const pair<int, int> & p1, const pair<int, int> & p2) {
	double dx = p1.first - p2.first;
	double dy = p1.second - p2.second;
	return dx * dx + dy * dy;
}

double solve(int lo, int hi) {
	double d = 1e20;
	if (hi - lo <= 3) {
		for (int i = lo; i < hi; i++) {
			for (int j = i + 1; j < hi; j++) {
				d = min(d, dis(A[i], A[j]));
			}
		}
	} else {
		int mid = (lo + hi) / 2;
		d = min(solve(lo, mid), solve(mid, hi));
		for (int i = mid - 1, c1 = 0; c1 < 8 && i >= lo; c1++, i--) {
			for (int j = mid, c2 = 0; c2 < 8 && j < hi; c2++, j++) {
				d = min(d, dis(A[i], A[j]));
			}
		}
	}
	return d;
}

int main() {
	ifstream cin("cmap.in");
	ofstream cout("cmap.out");
	cin >> n;
	A.reserve(n);
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		A.push_back(make_pair(x, y));
	}
	sort(A.begin(), A.end());
	cout << fixed << setprecision(6) << sqrt(solve(0, n));
	return 0;
}