내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
단순 다각형
ps:problems:boj:3679
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 단순 다각형 ====== ===== 풀이 ===== * [[ps:이론:각도 기준 정렬#단순 다각형 만들기]] 참고. 점들을 각도순으로 정렬한 뒤에, 처음과 마지막 부분의 점들만 각도가 같은 경우 거리를 기준으로 다시 정렬해주면 된다. 시간복잡도는 O(nlogn). ===== 코드 ===== <dkpr py> """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() </dkpr> * Dependency: [[:ps:teflib:geometry#polar_angle_key|teflib.geometry.polar_angle_key]] {{tag>BOJ ps:problems:boj:플래티넘_4}}
ps/problems/boj/3679.txt
· 마지막으로 수정됨: 2023/04/26 05:57 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로