Cod sursa(job #2077436)

Utilizator serfidenSilav Cristian Alexandru serfiden Data 28 noiembrie 2017 08:08:58
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.9 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

struct point{
	int x;
	int y;
};

int pseudoDistance(point first, point second) {
	int paramA = (int)pow((first.x - second.x), 2);
	int paramB = (int)pow((first.y - second.y), 2);
	return paramA + paramB;
}

bool sortingUtilityAbscissa(point first, point second) {
	return (first.x <= second.x);
}

bool sortingUtilityOrdinate(point first, point second) {
	return (first.y <= second.y);
}

int mergeDistances(std::vector<point> &pointsArray, int leftBound, int rightBound, int &partialMinimum) {
	std::vector<point> sortedArray;
	std::vector<point> potentialPoints;

	int median = (leftBound + rightBound) / 2;
	point middlePoint = pointsArray[median];

	int leftSubsetIndex = leftBound;
	int rightSubsetIndex = median + 1;
	while (leftSubsetIndex <= median && rightSubsetIndex <= rightBound) {
		
		if (pointsArray[leftSubsetIndex].y < pointsArray[rightSubsetIndex].y) {
			
			if (abs(middlePoint.x - pointsArray[leftSubsetIndex].x))
				potentialPoints.push_back(pointsArray[leftSubsetIndex]);

			sortedArray.push_back(pointsArray[leftSubsetIndex]);
			leftSubsetIndex ++;

		} else {
			
			if (abs(middlePoint.x - pointsArray[rightSubsetIndex].x))
				potentialPoints.push_back(pointsArray[rightSubsetIndex]);

			sortedArray.push_back(pointsArray[rightSubsetIndex]);
			rightSubsetIndex ++;
		}
	}

	if (leftSubsetIndex <= median) {
		while (leftSubsetIndex <= median) {
			if (abs(middlePoint.x - pointsArray[leftSubsetIndex].x))
				potentialPoints.push_back(pointsArray[leftSubsetIndex]);

			sortedArray.push_back(pointsArray[leftSubsetIndex]);
			leftSubsetIndex ++;
		}
	} else if (rightSubsetIndex <= rightBound) {
		if (abs(middlePoint.x - pointsArray[rightSubsetIndex].x))
				potentialPoints.push_back(pointsArray[rightSubsetIndex]);

			sortedArray.push_back(pointsArray[rightSubsetIndex]);
			rightSubsetIndex ++;
	}

	for (int i = leftBound; i <= rightBound; i ++) pointsArray[i] = sortedArray[i - leftBound];

	for (int i = 0; i < potentialPoints.size() - 1; i ++) 
		for (int j = i + 1; j < potentialPoints.size() && j < 8 - i; j ++) {
			int potentialMinimalDistance = pseudoDistance(potentialPoints[i], potentialPoints[j]);
			if (potentialMinimalDistance && potentialMinimalDistance < partialMinimum) 
				partialMinimum = potentialMinimalDistance;
		}

}

int minimalDistance(std::vector<point> &pointsArray, int leftBound, int rightBound) {
	if (rightBound - leftBound == 1) {
		return pseudoDistance(pointsArray[leftBound], pointsArray[rightBound]);
	
	} else if (rightBound - leftBound == 2) {
		std::vector<int> discreteAux(3);
		discreteAux[0] = pseudoDistance(pointsArray[leftBound], pointsArray[leftBound + 1]);
		discreteAux[1] = pseudoDistance(pointsArray[leftBound + 1], pointsArray[rightBound]);
		discreteAux[2] = pseudoDistance(pointsArray[rightBound], pointsArray[leftBound]);

		std::sort(discreteAux.begin(), discreteAux.end());
		return discreteAux[2];
	
	} else {
		int median = (leftBound + rightBound) / 2;
		
		int partialMinimalDistance = min(minimalDistance(pointsArray, leftBound, median),
									minimalDistance(pointsArray, median + 1, rightBound)); 
		
		mergeDistances(pointsArray, leftBound, rightBound, partialMinimalDistance);
		return partialMinimalDistance;
	}
}

int main() {
	std::vector<point> pointsArray;
	int pointsNumber;
	ifstream f;

	f.open("cmap.in");
	f >> pointsNumber;
	for (int i = 0; i < pointsNumber; i ++) {
		point newPoint;
		f >> newPoint.x;
		f >> newPoint.y;
		pointsArray.push_back(newPoint);
	}

	ofstream o;
	o.open("cmap.out");

	sort(pointsArray.begin(), pointsArray.end(), sortingUtilityAbscissa);
	o << fixed << setprecision(6) << sqrt(minimalDistance(pointsArray, 0, pointsArray.size() - 1));

	f.close();
	o.close();
	return 0;
}