사용자 도구

사이트 도구


ps:problems:boj:3679

단순 다각형

ps
링크acmicpc.net/…
출처BOJ
문제 번호3679
문제명단순 다각형
레벨플래티넘 4
분류

기하학

시간복잡도O(T*nlogn)
인풋사이즈T<=200, n<=2000
사용한 언어Python 3.11
제출기록36468KB / 108ms
최고기록108ms
해결날짜2023/04/26

풀이

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

토론

댓글을 입력하세요:
Y W V M D
 
ps/problems/boj/3679.txt · 마지막으로 수정됨: 2023/04/26 05:57 저자 teferi