#include #include #include #include #include #include //#include using std::vector; using std::min; struct Point { int x, y; bool operator==(const Point &p1) { return (x == p1.x && y == p1.y); } }; bool sortPointXDimension(Point i, Point j) { if (i.x == j.x) { return i.y < j.y; } return i.x < j.x; } bool sortPointYDimension(Point i, Point j) { if (i.y == j.y) { return i.x < j.x; } return i.y < j.y; } float distance(Point p1, Point p2) { return pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2); } float baseCaseMinDistance(vector &ptsVector, int low, int high) { if (high - low == 1) return distance(ptsVector[low], ptsVector[high]); if (high - low == 2) { float f1 = distance(ptsVector[low], ptsVector[low + 1]); float f2 = distance(ptsVector[low], ptsVector[high]); float f3 = distance(ptsVector[high], ptsVector[low + 1]); return min(f1, min(f2, f3)); } float f1 = distance(ptsVector[low], ptsVector[low + 1]); float f2 = distance(ptsVector[low], ptsVector[low + 2]); float f3 = distance(ptsVector[low], ptsVector[high]); float f4 = distance(ptsVector[low + 1], ptsVector[low + 2]); float f5 = distance(ptsVector[low + 1], ptsVector[high]); float f6 = distance(ptsVector[low + 2], ptsVector[high]); return min(f1, min(f2, min(f3, min(f4, min(f5, f6))))); } float dPrimeDistance(vector &shadedPoints) { float minDistance = FLT_MAX; float tempDistance; for (int i = 0; i < shadedPoints.size(); i++) { for (int j = 1; j <= 5; j++) { if (i + j < shadedPoints.size()) { tempDistance = distance(shadedPoints[i], shadedPoints[i + j]); minDistance = min(tempDistance, minDistance); } } } return minDistance; } float minimalDistance(vector &ptsVector, int low, int high) { if (high - low <= 3) { return baseCaseMinDistance(ptsVector, low, high); } int mid = low + (high - low) / 2; long midX = ptsVector[mid].x; float f1 = minimalDistance(ptsVector, low, mid - 1); float f2 = minimalDistance(ptsVector, mid, high); float f = min(f1, f2); vector shadedPoints; for (int i = low; i <= high; i++) { if (abs(ptsVector[i].x - midX) <= f) shadedPoints.push_back(ptsVector[i]); } std::sort(shadedPoints.begin(), shadedPoints.end(), sortPointYDimension); float fPrime = dPrimeDistance(shadedPoints); return min(f, fPrime); } float minimalDistance(vector &x, vector &y) { vector ptsVector(x.size()); Point tempP; for (int i = 0; i < x.size(); i++) { tempP = {x[i],y[i]}; ptsVector[i] = tempP; } std::sort(ptsVector.begin(), ptsVector.end(), sortPointXDimension); return sqrt(minimalDistance(ptsVector, 0, ptsVector.size() - 1)); } //TEST(SortPoint, Sort1) { // vector x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 }; // vector y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 }; // vector p; // Point tempP; // // for (int i = 0; i < x.size(); ++i) { // tempP = {x[i],y[i]}; // p.push_back(tempP); // }; // // std::sort(p.begin(), p.end(), sortPointXDimension); // // ASSERT_EQ(p[0].x, -4); // ASSERT_EQ(p[0].y, 0); // // std::sort(p.begin(), p.end(), sortPointYDimension); // ASSERT_EQ(p[0].y, -4); // ASSERT_EQ(p[0].x, -3); // ASSERT_EQ(p[10].y, 4); // ASSERT_EQ(p[10].x, 4); //} // //TEST(PointDistance, Test1) { // vector x = { 0, 0 }; // vector y = { 3, 4 }; // // float f = minimalDistance(x, y); // ASSERT_FLOAT_EQ(f, 5); //} // //TEST(ClosestDistance, Test1) { // vector x = { 0, 3 }; // vector y = { 0, 4 }; // float result = 5.0; // ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); //} // //TEST(ClosestDistance, Test2) { // vector x = { 0, 3, 5 }; // vector y = { 0, 4, 6 }; // float result = 2.828427; // ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); //} // //TEST(ClosestDistance, Test3) { // vector x = { 7, 1, 4, 7 }; // vector y = { 7, 100, 8, 7 }; // float result = 0.0; // ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); //} // //TEST(ClosestDistance, Test4) { // vector x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 }; // vector y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 }; // float result = 1.4142135; // ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); //} int main() { size_t n; std::cin >> n; vector x(n); vector y(n); for (size_t i = 0; i < n; i++) { std::cin >> x[i] >> y[i]; } std::cout << std::fixed; std::cout << std::setprecision(9) << minimalDistance(x, y) << "\n"; }