Pagini recente » Cod sursa (job #1911861) | Cod sursa (job #256837) | Istoria paginii runda/grigore-moisil-2017-clasa-10/clasament | Cod sursa (job #1138835) | Cod sursa (job #2077436)
#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;
}