농장 울타리 설계 (스몰)

문제

넓은 농장을 사서 그 둘레에 울타리를 세우려고 한다. 농장에는 이미 울타리 기둥이 $N$ 개 서 있다.

울타리는 기둥과 기둥을 직선으로 이어서 만든다. 변호사가 기둥을 하나도 남기지 말라고 하니 $N$ 개를 모두 써야 한다.

기둥은 평면 위의 점이다. 기둥의 순서를 하나 정한 다음 첫 번째와 두 번째, 두 번째와 세 번째를 차례로 잇고, 마지막 기둥을 다시 첫 번째 기둥에 이어 울타리를 완성한다. 완성된 울타리는 자기 자신과 교차하지 않는 다각형이어야 한다. 즉 각 기둥에는 울타리 구간이 정확히 두 개 닿고, 기둥이 아닌 점을 지나는 울타리 구간은 많아야 하나다.

울타리를 세운 뒤에도 농장은 넓어야 한다. 기둥을 일부만 골라 써도 된다고 할 때 둘러쌀 수 있는 최대 넓이를 $M$ 이라고 하자. $N$ 개를 모두 쓰는 울타리가 둘러싸는 넓이는 $M/2$ 보다 커야 한다.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 기둥의 수 $N$ 이 주어진다. 기둥의 번호는 0부터 $N-1$ 까지다. 이어지는 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번 기둥의 좌표 $X_i$ 와 $Y_i$ 가 공백 하나를 사이에 두고 주어진다.

제한

기둥 $N$ 개의 위치는 모두 다르고, 전부 한 직선 위에 있지는 않다.
$1 \le T \le 100$
$3 \le N \le 10$
$-100 \le X_i, Y_i \le 100$

출력

각 테스트 케이스마다 한 줄에 "Case #x: "를 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호다. 그 뒤에 0부터 $N-1$ 까지의 서로 다른 정수 $N$ 개를 공백으로 구분해 출력한다. 이 수열이 울타리를 세우는 기둥의 순서이며, 시계 방향과 반시계 방향 중 어느 쪽이어도 된다. 마지막 기둥은 첫 기둥과 이어진다.

조건을 만족하는 순서는 여러 개일 수 있다. 그중 사전순으로 가장 작은 하나만 출력한다. 즉 가능한 순서를 길이 $N$ 의 수열로 보고 사전순으로 비교해 가장 작은 것을 고른다. 위 제한에서 답은 항상 존재한다.

힌트

첫 번째 예제 데이터의 기둥 네 개로 만들 수 있는 다각형은 세 가지다. 넓이 조건을 만족하는 것은 0 1 2 3과 0 2 1 3이고, 0 1 3 2는 넓이가 정확히 $M/2$ 라서 조건에 못 미친다. 둘 중 사전순으로 앞서는 0 1 2 3이 답이다.

두 번째 예제 데이터에서는 울타리가 스스로 교차하지 않는지 살펴야 한다. 0 1 2 3 4는 3번 기둥과 4번 기둥을 잇는 구간이 1번 기둥을 지나가므로 울타리가 될 수 없다.

세 번째 예제 데이터는 기둥이 셋뿐이라 어떤 순서든 같은 삼각형이 된다. 사전순으로 가장 작은 0 1 2가 답이다.