아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

삼각형 분할

시간 제한1초메모리 제한256 MB

요약
세 점이 한 직선 위에 있지 않은 3n개의 점을 n개의 서로 겹치지 않는 삼각형으로 나누고, 각 삼각형이 사용하는 점의 번호를 출력한다.
난이도

보통10점 중 6점

유형
기하, 정렬, 그리디, 구현
정답자
아직 제출이 없습니다

문제

Chiaki에게는 3n3n개의 점 p1,p2,…,p3np_1,p_2,\dots,p_{3n}이 있다. 어느 세 점도 한 직선 위에 있지 않다.

Chiaki는 3n3n개의 점을 꼭짓점으로 사용해 서로 겹치지 않는 nn개의 삼각형을 만들려고 한다.

입력

여러 개의 테스트 케이스가 주어진다. 입력의 첫째 줄에는 테스트 케이스의 수 TT가 주어진다. 각 테스트 케이스는 다음과 같다.

첫째 줄에는 만들 삼각형의 수 nn이 주어진다. (1≤n≤10001 \le n \le 1000)

다음 3n3n개의 줄에는 두 정수 xix_i와 yiy_i가 주어진다. (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9)

모든 nn의 합은 10410^4를 넘지 않는다.

출력

각 테스트 케이스마다 nn개의 줄을 출력한다. 각 줄에는 ii번째 삼각형이 사용하는 점의 번호 ai,bi,cia_i,b_i,c_i를 출력한다. (1≤ai,bi,ci≤3n1 \le a_i,b_i,c_i \le 3n) 답이 여러 가지라면 그중 아무거나 출력해도 된다.

예제1

  1. 예제 1

    입력
    1
    1
    1 2
    2 3
    3 5
    
    예상 출력
    1 2 3