Cod sursa(job #1618453)

Utilizator cristighrCristi Gherghina cristighr Data 27 februarie 2016 20:19:49
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

long int n;

typedef struct Point {
	long int x;
	long int y;
} Point;

vector<Point> pVector;
#define INF 0x7fffffff

void read() {
	ifstream fin("cmap.in");

	long int x, y;
	fin >> n;

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

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

		pVector.push_back(p);
	}

	fin.close();
}

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

void sortX() {
	sort(pVector.begin(), pVector.end(), wayToSortX);
}

void display() {
	for (int i = 0; i < n; i++)
		cout << pVector[i].x << " " << pVector[i].y << endl;
	getchar();
}

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(int left, int right) {
	double d = INF;

	for (int i = left; i < right - 1; i++)
		for (int j = i + 1; j < right; j++)
			d = min(d, distance(pVector[i], pVector[j]));
}

long double findMinDistance(int start, int end) {
	if (end - start <= 2)
		return threePoints(start, end);

	int mid = (start + end) / 2;

	double d = min(findMinDistance(start, mid), findMinDistance(mid + 1, end));

	int xmid = pVector[n / 2].x;

	vector<Point> midRegion;
	for (int i = 0; i < n / 2; i++) {
		if (abs(pVector[i].x - xmid) < d)
			midRegion.push_back(pVector[i]);
	}
	for (int i = n / 2; i < n; i++) {
		if (abs(pVector[i].x - xmid) < d)
			midRegion.push_back(pVector[i]);
	}

	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()
{
	std::ofstream fout("cmap.out");
	read();
	sortX();

	fout << std::fixed << findMinDistance(0, n - 1) << '\n';

	return 0;
}