Cod sursa(job #1093898)

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

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

struct ComparerY {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.second < b.second;
	}
};

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

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

		double result() { 
			return sqrt(1.0 * (double)v);
		}
	private:
		vector<pair<int,int> > points;
		long long v;

		long long divide(int low, int high) {
			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 m = (low+high) / 2;
			result = min(result, divide(low, m));
			result = min(result, divide(m + 1, high));

			vector<pair<int, int> > Y;
			for (int i=m; points[m].first - points[i].first <= result && i>=0; --i) Y.push_back(points[i]);
			for (int i=m+1; points[i].first - points[m].first <= result && i<points.size(); ++i) Y.push_back(points[i]);
			ComparerY comp;
			sort(Y.begin(), Y.end(), comp);

			for (int i=0; i<Y.size(); ++i) {
				for (int j=i+1; j-i <= 7 && j<Y.size(); ++j) {
					result = min(result, dist(Y[i], Y[j]));
				}
			}

			return result;
		}

		long long dist(int x, int y) { 
			return ((long long)points[x].first - points[y].first) * ((long long)points[x].first - points[y].first) + 
				   ((long long)points[x].second - points[y].second) * ((long long)points[x].second - points[y].second);
		}
		long long dist(pair<int, int> x, pair<int, int> y) {
			return ((long long)x.first - y.first) * ((long long)x.first - y.first) + 
				   ((long long)x.second - y.second) * ((long long)x.second - 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 << fixed << setprecision(6) << cp.result() << "\n";
	return 0;
}