[백준] 11650 좌표 정렬하기

좌표 정렬하기 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

136597

65405

50827

48.023%

문제

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

 

#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;

typedef struct Coordinate {
	int x;
	int y;
}UserCoordinate;

bool compare_coordinate(const Coordinate& a, const Coordinate& b) {
	if (a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}

int main() {
	int size = 0;
	cin >> size;

	UserCoordinate* p = (UserCoordinate*)malloc(sizeof(UserCoordinate) * size);

	for (int i = 0; i < size; i++) {
		cin >> p[i].x;
		cin >> p[i].y;
	}

	sort(p, p + size, compare_coordinate);

	for (int i = 0; i < size; i++) {
		cout << p[i].x << " ";
		cout << p[i].y << "\n";
	}

	free(p);

	return 0;
}

 

c언어와 달리 c++의 sort(algorithm 헤더에 정의)함수는 포인터 접근이 아닌 값에 의한 접근을 하므로 

compare함수의 인자는 포인터(*)가 아닌 값(&)으로 정의해야 한다.

 

부등호의 방향은 오름차순 기준으로 정렬이 필요없는 경우 1을 반환하도록 작성해야 한다.

(c의 qsort의 경우 정렬이 필요없는 경우 음수를 반환하도록)