[백준 11650] 좌표 정렬하기

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

1/7일 문제

 

요구사항

좌표 정렬하기

1. x 오름차순

2. y 오름차순

 

풀이

머지 소트로 정렬하기

 

#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;
 
const int PN = 23;
const int HASH_SIZE = 10000;


struct go{
    int x;
    int y;
};
go map[100001];
go buf[100001];

int n;
/*
void qasort(int arr[], int left, int right){
    if(left>=right){
        return;
    }
    int i = left;
    int j = right;
    int pivot = arr[(left+right)/2];

    while(i<=j){
        while(arr[i]<pivot){
            i++;
        }
        while(arr[j]>pivot){
            j--;
        }
        if(i<=j){
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
            i++;
            j--;
        }
    }
    qasort(arr,left,j);
    qasort(arr,i,right);
}
*/
/*
void merge_sort(int arr[], int len){
    
    if(len<2)
        return;
    int i,j,mid,k;
    mid = len/2;
    i=0;
    k=0;
    j=mid;

    merge_sort(arr,mid);
    merge_sort((arr+mid),(len-mid));

    while(i<mid && j<len){
        if(arr[i]<arr[j]){
            buf[k++]=arr[i++];
        }
        else{
            buf[k++]=arr[j++];
        }
    }

    while(i<mid){
        buf[k++]=arr[i++];
    }

    while(j<mid){
        buf[k++]=arr[j++];
    }

    for(int i =0 ; i <len ; i++){
        arr[i]=buf[i];
    }
}
*/
void merge_sort(go arr[], int len)
{
    if(len<2){
        return;
    }
    int i,j,k,mid;
    mid=len/2;
    i=0;
    j=mid;
    k=0;
    merge_sort(arr,mid);
    merge_sort((arr+mid),(len-mid));
    while(i<mid && j<len){
        if(arr[i].x <arr[j].x){
            buf[k++]=arr[i++];
        }
        else if(arr[i].x == arr[j].x){
            if(arr[i].y <= arr[j].y){
                buf[k++] = arr[i++];
            }
            else{
                buf[k++]=arr[j++];
            }
        }
        else{
            buf[k++]=arr[j++];
        }
    }

    while(i<mid){
        buf[k++]=arr[i++];
    }

    while(j<len){
        buf[k++]=arr[j++];
    }
    for(int a =0 ; a < len ; a++){
        arr[a]=buf[a];
    }

}
/*
void qasort(go arr[], int left, int right){
    if(left>=right)
        return;
    int i = left;
    int j = right;
    go pivot= arr[(left+right)/2];

    while(i<=j){
        while(arr[i].size < pivot.size){
            i++;
        }
        
        while(arr[j].size > pivot.size){
            j--;
        }
        if(arr[i].size == arr[j].size){
            for(int k=0 ; k<arr[i].size ; k++){
                if(arr[i].ch[j] > arr[j].ch[j]){

                }
                else{

                }
            }
        }
        if(i<=j){
            go temp;
            temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
            i++;
            j--;
        }
    }
    qasort(arr,left,j);
    qasort(arr,i,right);
}
void merge_sort(go arr[], int len){
    if(len<2){
        return;
    }
    int i,j,mid,k;
    mid=len/2;
    i=0;
    j=mid;
    k=0;
    merge_sort(arr,mid);
    merge_sort((arr+mid),(len-mid));

    while(i<mid && j <len){
        
        if(arr[i].size < arr[j].size){
            buf[k++]=arr[i++];
        }
        
        else if(arr[i].size == arr[j].size){
          //  cout<<arr[i].size<<endl;
            int flag=0;
            for(int len=0 ; len<arr[i].size ; len++){
         //       cout<<arr[i].ch[len]<<" "<<arr[j].ch[len]<<endl;
                if(arr[i].ch[len] < arr[j].ch[len]){
                    buf[k++]=arr[i++];
                    flag=1;
                    break;;
                }
                else if(arr[i].ch[len] > arr[j].ch[len]){
                    buf[k++]=arr[j++];
                    flag=1;
                    break;;
                }
            }
            if(flag==1)
                continue;
            else{
                buf[k++]=arr[i++];}

        }
        else{
            buf[k++]=arr[j++];
        }
    }

    while(i<mid){
        buf[k++]=arr[i++];
    }

    while(j<len){
        buf[k++]=arr[j++];
    }

    for(int k=0 ; k <len ; k++){
        arr[k]=buf[k];
    }

}
int strcmp(char a[], char b[])
{
    int i=0;
    int j=0;
    while(a[i]){
        if(a[i++] != b[j++]){
            i--,j--;
            break;
        }
    }
    return a[i]-b[j];
}
*/
int main(){
 //   cout<<"A"<<endl;
    scanf("%d",&n);
    for(int i=0 ; i <n;i++){
        scanf("%d%d",&map[i].x,&map[i].y);
    }
    merge_sort(map,n);
  //  cout<<endl;
    for(int i=0 ; i < n ; i++){
        printf("%d %d\n",map[i].x,map[i].y);
    }
   // cout<<"AAAAAAAAA"<<endl;
}