import sys,math
input = sys.stdin.readline
for _ in range(int(input())):
data = [*map(int,input().split())]; N = data[0]
co = sorted([(data[i*2+2],data[i*2+1],i) for i in range(N)])
y0,x0,n0 = co[0]; stack = []
for i in range(1,N):
y,x,n = co[i]
d = math.sqrt((x-x0)**2+(y-y0)**2)
stack.append((int((x0-x)/d*1e9),int(d*1e9),n))
stack.sort()
cos0 = stack[-1][0]
for i in range(N-1):
if stack[-i-1][0]!=cos0:
break
stack = stack[:-i]+sorted(stack[-i:],reverse=True)
print(n0,*map(lambda x:x[2],stack))
볼록껍질 응용(?) 문제
볼록껍질 문제에서 그레이엄 스캔을 하기 전에 점들을 각도에 따라 정렬을 해주게 된다. 이 문제는 그냥 이때의 정렬된 순서를 출력하면 끝나는 문제이다. 그래서 구현난이도는 볼록껍질의 하위호환 문제라고 볼 수 있다.
약간의 예외처리가 필요한데,
1. 각도가 같은 경우에는 거리의 오름차순으로 정렬한다.
2. 맨 마지막 값들의 각도가 같은 경우에는 거리의 내림차순으로 정렬한다.
3. 소수를 그대로 계산하면 각도가 같은 경우에도 다르다고 판단하고 잘못된 결과를 도출할 수 있으니 소수점 10의자리 정도에서 반올림해주는 것이 좋다.
3번 때문에 애먹은 문제였다. 각도의 계산을 코사인으로 해주었는데, 소수점 차이때문에 계속 틀렸습니다가 나왔었다. 따라서 소수에 10**9를 곱하고 int형으로 변환하자 맞게되었다.
오늘의 교훈) 볼록껍질 정렬과정에서 소수점 차이 조심