[acmicpc] 11650 좌표 정렬하기 정답 코드

#include <stdio.h> 
#include <stdlib.h>
 
typedef struct _Point
{
    int m_X;
    int m_Y;
    bool operator>(struct _Point& other) const;
} Point;
 
typedef Point *Points;
 
bool _Point::operator>(_Point& other) const
{
    if (this->m_X > other.m_X)
    {
        return true;
    }
    else if (this->m_X == other.m_X)
    {
        if (this->m_Y > other.m_Y)
        {
            return true;
        }
    }
    return false;
}
 
void merge(Points* arr, int start1, int end1, int start2, int end2)
{
    // 앞 배열의 인덱스와 뒤 배열의 인덱스 
    int i = start1, j = start2;
 
    // 임시 배열 (정렬을 위한)
    int nArrSize = end2 - start1 + 1;
    int index = 0;
    Points pTemp = (Points)malloc(sizeof(Point) * nArrSize);
 
    // 두 배열을 오름차순으로 pTemp에 저장 
    while (i <= end1 || j <= end2)
    {
        // 배열 index out of bound 오류 방지
        if (i > end1)
        {
            (pTemp + index)->m_X = (*arr + j)->m_X;
            (pTemp + index)->m_Y = (*arr + j)->m_Y;
            index++; j++;
        }
        else if (j > end2)
        {
            (pTemp + index)->m_X = (*arr + i)->m_X;
            (pTemp + index)->m_Y = (*arr + i)->m_Y;
            index++; i++;
        }
        else if ((*(*arr + i)) > (*(*arr + j)))
        {
            (pTemp + index)->m_X = (*arr + j)->m_X;
            (pTemp + index)->m_Y = (*arr + j)->m_Y;
            index++; j++;
        }
        else
        {
            (pTemp + index)->m_X = (*arr + i)->m_X;
            (pTemp + index)->m_Y = (*arr + i)->m_Y;
            index++; i++;
        }
    }
 
    // pTemp 배열을 본래 arr 배열에 복사
    for (int i = 0; i < nArrSize; i++)
    {
        (*arr + start1 + i)->m_X = (pTemp + i)->m_X;
        (*arr + start1 + i)->m_Y = (pTemp + i)->m_Y;
    }
 
    free(pTemp);
}
 
void mergeSort(Points* arr, int start, int end)
{
    // 종료 조건 
    if (start >= end) return;
 
    int nMid = (start + end) / 2;
 
    // 정렬이 된 배열 = 정렬이 된 배열의 절반 2개를 정렬하면서 합친 것이다. 
    mergeSort(arr, start, nMid);
    mergeSort(arr, nMid + 1, end);
    merge(arr, start, nMid, nMid + 1, end);
}
 
int main(void)
{
    unsigned int nInput;
    scanf("%u", &nInput);
 
    Points points = (Points)malloc(sizeof(Point) * nInput);
 
    for (unsigned int i = 0; i < nInput; i++)
    {
        scanf(" %d %d", &((points + i)->m_X), &((points + i)->m_Y));
    }
 
    mergeSort(&points, 0, nInput - 1);
 
    for (unsigned int i = 0; i < nInput; i++)
    {
        printf("%d %d\n", (points + i)->m_X, (points + i)->m_Y);
    }
 
    free(points);
 
    return 0;
}
 

 

상당히 길게 짯습니다..