CountingSortOfPoints

#include <iostream>
#include <vector>
using namespace std;

struct CPoint {
    int X;
    int Y;

    CPoint( int x, int y ) : X( x ), Y( y ) {}
};

// Сортировка точек по X.
void CountingSort( vector<CPoint>& arr, int maxValue )
{
    vector<int> counts( maxValue + 1, 0 );
    // Считаем, сколько раз встретилось каждое число.
    for( int i = 0; i < static_cast<int>( arr.size() ); ++i ) {
        ++counts[static_cast<int>( arr[i].X )];
    }
    // Считаем начало каждой группы. Сохраним их в counts.
    int summ = 0;
    for( int i = 0; i < maxValue + 1; ++i ) {
        int temp = counts[i];
        counts[i] = summ;
        summ += temp;
    }

    // Проходим по исходному массиву и заполняем временный массив с результатом. Размера arr.
    vector<CPoint> destination( arr.size(), CPoint( 0, 0 ) );
    for( int i = 0; i < static_cast<int>( arr.size() ); ++i ) {
        destination[counts[arr[i].X]++] = arr[i];
    }
    std::swap( arr, destination ); // O(1).
}

int main()
{
    int n = 0;
    cin >> n;
    vector<CPoint> arr( n, CPoint( 0, 0 ) );
    for( int i = 0; i < n; ++i ) {
        cin >> arr[i].X >> arr[i].Y;
    }

    CountingSort( arr, 1000000 );

    for( int i = 0; i < n; ++i ) {
        cout << arr[i].X << ' ' << arr[i].Y << endl;
    }
    return 0;
}