삼각형으로 영토 나누기
면접 대비시간 제한1초메모리 제한16 MB
말뚝을 x좌표 순, 동점이면 y좌표 순으로 정렬한 뒤 앞에서부터 세 개씩 묶어 각 묶음의 입력 번호를 오름차순으로 출력합니다.
- 난이도
쉬움10점 중 2점
- 유형
- 정렬
- 정답자
- 아직 제출이 없습니다
문제
넓은 영토가 평면 위에 있고, 그 위에 말뚝이 정확히 개 박혀 있다. 말뚝의 위치는 모두 다르고, 어느 세 말뚝도 한 직선 위에 있지 않다.
명이 이 영토를 나눈다. 각자 말뚝을 3개씩 고르고, 고른 말뚝을 선분으로 이어 만든 삼각형의 안쪽을 자기 영토로 가진다. 모든 말뚝은 정확히 한 사람에게 배정된다. 서로 다른 두 사람의 삼각형은 경계선이나 꼭짓점에서도 만나면 안 된다.
이런 분할은 어떤 입력에서도 존재한다. 다만 분할이 여러 개일 수 있으므로, 다음 규칙으로 정해지는 분할 하나만 출력한다.
- 말뚝을 좌표가 작은 순으로 정렬한다. 좌표가 같으면 좌표가 작은 순으로 정렬한다. 말뚝의 위치가 모두 다르므로 이 순서는 하나로 정해진다.
- 정렬한 순서대로 앞에서부터 3개씩 끊는다. 앞의 3개가 첫 번째 사람, 그다음 3개가 두 번째 사람, 이런 식으로 번째 사람까지 배정한다.
이 규칙으로 나눈 삼각형은 서로 만나지 않는다.
입력
첫째 줄에 사람의 수 ()이 주어진다.
다음 개의 줄에 말뚝의 좌표 와 ()가 공백으로 구분되어 주어진다. 두 값은 모두 정수다. 말뚝에는 입력 순서대로 1번부터 번까지 번호가 붙는다. 말뚝의 위치는 모두 다르고, 어느 세 말뚝도 한 직선 위에 있지 않다.
출력
개의 줄을 출력한다. 번째 줄에는 위 규칙으로 번째 사람에게 배정된 말뚝 세 개의 번호를 번호가 커지는 순으로 공백으로 구분해 출력한다.