Untitled
unknown
plain_text
a year ago
2.0 kB
11
Indexable
#include <iostream> using namespace std; struct Point3D{ int x, y, z; }; bool cp(Point3D u, Point3D v){ if (u.x < v.x) return true; if (u.x == v.x) if (u.y > v.y) return true; else if (u.y == v.y) return (u.z < v.z); return false; } void merge(Point3D array[], int const left, int const mid, int const right) { int const subArrayOne = mid - left + 1; int const subArrayTwo = right - mid; auto *leftArray = new Point3D[subArrayOne], *rightArray = new Point3D[subArrayTwo]; for (auto i = 0; i < subArrayOne; i++) leftArray[i] = array[left + i]; for (auto j = 0; j < subArrayTwo; j++) rightArray[j] = array[mid + 1 + j]; auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0; int indexOfMergedArray = left; while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) { if (cp(leftArray[indexOfSubArrayOne], rightArray[indexOfSubArrayTwo])) { array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]; indexOfSubArrayOne++; } else { array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]; indexOfSubArrayTwo++; } indexOfMergedArray++; } while (indexOfSubArrayOne < subArrayOne) { array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]; indexOfSubArrayOne++; indexOfMergedArray++; } while (indexOfSubArrayTwo < subArrayTwo) { array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]; indexOfSubArrayTwo++; indexOfMergedArray++; } delete[] leftArray; delete[] rightArray; } void mergeSort(Point3D array[], int const begin, int const end) { if (begin >= end) return; int mid = begin + (end - begin) / 2; mergeSort(array, begin, mid); mergeSort(array, mid + 1, end); merge(array, begin, mid, end); } int main() { int N; cin >> N; Point3D a[N]; for (int i = 0; i < N; i++) cin >> a[i].x >> a[i].y >> a[i].z; mergeSort(a, 0, N-1); for (int i = 0; i < N; i++) cout << a[i].x << ' ' << a[i].y << ' ' << a[i].z << '\n'; return 0; return 0; }
Editor is loading...
Leave a Comment