BOJ 11650 - 좌표 정렬하기 [C]

문제

링크

풀이

#include <stdio.h>
 
struct dot {
	int x;
	int y;
};
 
void merge(struct dot d[], int l, int m, int r) { 
  int i, j, k; 
  int n1 = m-l+1; 
  int n2 = r-m; 
  struct dot L[n1], R[n2];
  
  for (i=0; i<n1; i++) {
    L[i].x = d[l+i].x; 
    L[i].y = d[l+i].y; 
	}
  for (j=0; j<n2; j++) {
    R[j].x = d[m+1+j].x; 
    R[j].y = d[m+1+j].y; 
	} 
	
	i=0, j=0, k=l;
  while (i<n1 && j<n2) { 
    if (L[i].x < R[j].x) { 
      d[k].x = L[i].x;
      d[k].y = L[i].y;
      i++; 
    } else if (L[i].x == R[j].x) {
			if (L[i].y <= R[j].y) {
				d[k].x = L[i].x;
				d[k].y = L[i].y;
				i++;
			} else {
				d[k].x = R[j].x;
				d[k].y = R[j].y;
				j++;
			}
		} else {
      d[k].x = R[j].x; 
      d[k].y = R[j].y; 
      j++; 
	  } 
    k++; 
  } 
  
  while (i < n1) { 
    d[k].x = L[i].x; 
    d[k].y = L[i].y; 
    i++, k++; 
  } 
 
  while (j < n2) { 
    d[k].x = R[j].x; 
    d[k].y = R[j].y; 
    j++, k++; 
  } 
} 
  
void mergeSort(struct dot d[], int l, int r) { 
  if (l < r) { 
    int m = l+(r-l)/2;
  
    mergeSort(d, l, m); 
    mergeSort(d, m+1, r); 
    merge(d, l, m, r); 
  } 
} 
  
int main(void) {
	int n;
	struct dot d[100001];
 
	scanf("%d", &n);
	for (int i=0; i<n; i++)
		scanf("%d %d", &d[i].x, &d[i].y);
 
	mergeSort(d, 0, n-1);
 
	for (int i=0; i<n; i++)
		printf("%d %d\n", d[i].x, d[i].y);
	return 0;
}