• 단순 다각형 만들기 참고. 점들을 각도순으로 정렬한 뒤에, 처음과 마지막 부분의 점들만 각도가 같은 경우 거리를 기준으로 다시 정렬해주면 된다. 시간복잡도는 O(nlogn).

"""Solution code for "BOJ 3679. 단순 다각형".

- Problem link: https://www.acmicpc.net/problem/3679
- Solution link: http://www.teferi.net/ps/problems/boj/3679

Tags: [geometry]
"""


import bisect
import math
from teflib import geometry


def main():
    c = int(input())
    for _ in range(c):
        n, *coords = [int(x) for x in input().split()]
        points = [(x, y) for x, y in zip(coords[::2], coords[1::2])]

        pole = min(points)
        get_angle = geometry.polar_angle_key(pole)
        angles = [get_angle(p) for p in points]
        answer = sorted(range(n), key=angles.__getitem__)

        first_angle = angles[answer[1]]
        pos = bisect.bisect_right(answer, first_angle, key=angles.__getitem__)
        answer[1:pos] = sorted(
            answer[1:pos], key=lambda i: math.dist(points[i], pole)
        )

        last_angle = angles[answer[-1]]
        pos = bisect.bisect_left(answer, last_angle, key=angles.__getitem__)
        answer[pos:] = sorted(
            answer[pos:], key=lambda i: -math.dist(points[i], pole)
        )

        print(*answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.geometry.polar_angle_key