사용자 도구

사이트 도구


ps:problems:boj:4181

Convex Hull

ps
링크acmicpc.net/…
출처BOJ
문제 번호4181
문제명Convex Hull
레벨플래티넘 5
분류

기하학

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

풀이

  • 볼록 껍질 (Convex Hull)을 만드는 알고리즘을 알아야 될 것 같은 제목이지만, 실제로는 이미 볼록껍질을 이루는 점들이 골라져 있기 때문에, 점들을 각도 기준 정렬 만 하면 된다.
  • 주의할 점은, 문제에서는 내각이 180도가 되는 꼭짓점들도 볼록껍질에 포함되어있다는 것이다. 단순 다각형 만들기에서 설명했던 것과 동일한 처리가 필요하다.
  • 결국, 사실상 단순 다각형와 동일한 문제이다.

코드

"""Solution code for "BOJ 4181. Convex Hull".

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

Tags: [geometry]
"""

import bisect
import math
import sys
from teflib import geometry


def main():
    n = int(sys.stdin.readline())
    points = []
    for _ in range(n):
        x, y, c = sys.stdin.readline().split()
        if c == 'Y':
            points.append([int(x), int(y)])

    pole = min(points)
    get_angle = geometry.polar_angle_key(pole)
    points.sort(key=get_angle)

    first_angle = get_angle(points[1])
    pos = bisect.bisect_right(points, first_angle, key=get_angle)
    points[1:pos] = sorted(points[1:pos], key=lambda p: math.dist(p, pole))

    last_angle = get_angle(points[-1])
    pos = bisect.bisect_left(points, last_angle, key=get_angle)
    points[pos:] = sorted(points[pos:], key=lambda p: -math.dist(p, pole))

    print(len(points))
    for p in points:
        print(*p)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
B D Q N G
 
ps/problems/boj/4181.txt · 마지막으로 수정됨: 2023/04/26 05:37 저자 teferi