Cod sursa(job #1618888)

Utilizator cristighrCristi Gherghina cristighr Data 28 februarie 2016 02:25:06
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

double n;

typedef struct Point {
	double x;
	double y;
} Point;

#define INF 0x7fffffff

bool wayToSortX (Point i, Point j) { 
	return i.x < j.x;
}
bool wayToSortY (Point i, Point j) {
	return i.y < j.y;
}

double distance(Point p, Point q) {
	return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
}

double threePoints(vector<Point> v) {
	double d = INF;

	for (int i = 0; i < v.size() - 1; i++)
		for (int j = i + 1; j < v.size(); j++)
			d = min(d, distance(v[i], v[j]));
}

vector<Point> slice(vector<Point> v, int start, int end) {
	vector<Point> nv;

	nv.assign(v.begin() + start, v.begin() + end);

	return nv;
}

double findMinDistance(vector<Point> v) {
	if (v.size() <= 3)
		return threePoints(v);

	int mid = v.size() / 2;
	int xmid = v[mid].x;

	double d = min(findMinDistance(slice(v, 0, mid + 1)), findMinDistance(slice(v, mid + 1, v.size())));

	int left, right;
	left = mid;
	right = mid;

	while (abs(v[left].x - xmid) < d)
		left--;
	while (abs(v[right].x - xmid) < d)
		right++;

	vector<Point> midRegion = slice(v, left, right);

	// sortez dupa y
	sort(midRegion.begin(), midRegion.end(), wayToSortY);

	for (int i = 0; i < midRegion.size(); i++)
		for (int j = 1; j < 8; j++)
			if (i + j < midRegion.size())
				d = min(d, distance(midRegion[i], midRegion[i + j]));

	return d;
}

int main()
{
	ifstream fin("cmap.in");
	std::ofstream fout("cmap.out");
	int x, y;

	fin >> n;

	vector<Point> pVector;

	while (fin >> x >> y) {
		Point p;

		p.x = x;
		p.y = y;

		pVector.push_back(p);
	}

	fin.close();

	// sortare dupa x a punctelor
	sort(pVector.begin(), pVector.end(), wayToSortX);

	cout << findMinDistance(pVector) << '\n';

	return 0;
}