사용자 도구

사이트 도구


ps:problems:boj:27123

Electric Fence

ps
링크acmicpc.net/…
출처BOJ
문제 번호27123
문제명Electric Fence
레벨실버 2
분류

기하학

시간복잡도O(logn)
인풋사이즈n<=65536
사용한 언어Python 3.11
제출기록33376KB / 44ms
최고기록40ms
해결날짜2023/04/10

풀이

  • 픽의 정리를 이용해서 삼각형 내부의 격자점의 갯수를 구하는 문제
  • 삼각형의 넓이가 m*p/2 로 간단히 계산되는 형태여서, 다각형의 넓이를 구하는 방법을 몰라도 풀 수 있는 문제이다.
  • 총 시간복잡도는 O(logn)

코드

"""Solution code for "BOJ 27123. Electric Fence".

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

Tags: [geometry] [pick's theorem]
"""


from teflib import geometry


def main():
    n, m, p = [int(x) for x in input().split()]
    interior_points, _ = geometry.lattice_point_in_polygon(
        [(0, 0), (n, m), (p, 0)]
    )
    print(interior_points)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L M J C V
 
ps/problems/boj/27123.txt · 마지막으로 수정됨: 2023/04/17 05:52 저자 teferi