Untitled

 avatar
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