<백준 알고리즘> 11651번: 좌표 정렬하기 2

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1

5 0 4 1 2 1 -1 2 2 3 3

예제 출력 1

1 -1 1 2 2 2 3 3 0 4

---

Solution

#include<stdio.h>
#include<stdlib.h>

int xtemp[100000], ytemp[100000];
void merge(int *x,int *y,int start,int end,int mid,int N)
{
	int i=start, j=mid+1;

	for(int k=	start;k<=end;k++)
		if(j>end)
		{
			xtemp[k]=x[i];
			ytemp[k]=y[i];
			i++;
		}
		else if(i>mid)
		{
			xtemp[k]=x[j];
			ytemp[k]=y[j];
			j++;
		}
		else if(y[i]<y[j] || y[i]==y[j]&&x[i]<x[j])
		{
			xtemp[k]=x[i];
			ytemp[k]=y[i];
			i++;
		}
		else
		{
			xtemp[k]=x[j];
			ytemp[k]=y[j];
			j++;
		}

	for(int k=start;k<=end;k++)
	{
		x[k]=xtemp[k];
		y[k]=ytemp[k];
	}
}

void mergesort(int *x,int *y,int start,int end,int N)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		mergesort(x,y,start,mid,N);
		mergesort(x,y,mid+1,end,N);
		merge(x,y,start,end,mid,N);
	}
}

int main(void)
{
	int N, *x=NULL, *y=NULL;

	scanf("%d", &N);
	x=(int *)malloc(N*sizeof(int));
	y=(int *)malloc(N*sizeof(int));

	for(int n=0;n<N;n++)
		scanf("%d %d", &x[n], &y[n]);

	mergesort(x,y,0,N-1,N);

	for(int n=0;n<N;n++)
		printf("%d %d\n", x[n], y[n]);
	free(x);
	free(y);
	return 0;
}