Cod sursa(job #1093882)

Utilizator cdt2014Cont de Teste cdt2014 Data 28 ianuarie 2014 18:42:23
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <vector>
#include <fstream>
#include <algorithm>
#include <complex>
#include <iomanip>
using namespace std;

struct Comparer {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.first < b.first || (a.first == b.first && a.second < b.second); 
	}
};

class ClosestPoints {
	public: 
		ClosestPoints(vector< pair<int,int> > points) {
			this->points = points;
			
			Comparer c;
			sort(points.begin(), points.end(), c);

			v = divide(0, points.size()-1, p1, p2);
		}

		float result() { 
			return sqrt(v);
		}
	private:
		vector<pair<int,int> > points;
		long long v;
		int p1, p2;

		long long divide(int low, int high, int& p1, int& p2) {
			long long result = 0x7fffffffLL * 0x7fffffffLL;
			if (high-low+1 <= 3) {
				for (int i=low; i<high; ++i)
					for (int j=i+1; j<=high; ++j) {
						result = min(result, dist(i, j));
					}
				return result;
			}

			int p1l, p2l, p1r, p2r;
			int m = (low+high) / 2;
			result = min(result, divide(low, m, p1l, p2l));
			result = min(result, divide(m + 1, high, p1r, p2r));

			int ll = m,
				hh = m;
			int x = points[m].first;
			while (points[m].first - points[ll].first < x && ll > 0) ll--;
			while (points[hh].first - points[m].first < x && hh < high) hh++;
			for (int i=ll; i<hh; ++i) {
				for (int j=i+1; j-i <= 7 && j<=hh; ++j) {
					result = min(result, dist(i, j));
				}
			}

			return result;
		}

		long long dist(int x, int y) { 
			return (points[x].first - points[y].first) * (points[x].first - points[y].first) + 
				   (points[x].second - points[y].second) * (points[x].second - points[y].second);
		}
};

int main() {
	ifstream in("cmap.in");
	ofstream out("cmap.out");
	vector<pair<int, int> > points;
	int N;

	in >> N;
	for (int i=0; i<N; ++i) {
		int x, y;
		in >> x >> y;
		points.push_back(make_pair(x, y));
	}

	ClosestPoints cp(points);
	out << setprecision(9) << cp.result() << "\n";
	return 0;
}