문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.
예제 입력 1
5 3 4 1 1 1 -1 2 2 3 3 |
예제 출력 1
1 -1 1 1 2 2 3 3 3 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(x[i]<x[j] || x[i]==x[j]&&y[i]<y[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;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 10814번: 나이순 정렬 (0) | 2021.06.25 |
---|---|
<백준 알고리즘> 11651번: 좌표 정렬하기 2 (0) | 2021.06.25 |
<백준 알고리즘> 11055번: 가장 큰 증가 부분 수열 (0) | 2021.06.22 |
<백준 알고리즘> 14002번: 가장 긴 증가하는 부분 수열 4 (0) | 2021.06.22 |
<백준 알고리즘> 2011번: 암호코드 (0) | 2021.06.22 |