Electric Fence

• 픽의 정리를 이용해서 삼각형 내부의 격자점의 갯수를 구하는 문제
• 삼각형의 넓이가 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()

• Dependency: teflib.geometry.lattice_point_in_polygon