사용자 도구

사이트 도구


ps:problems:boj:7694

Triangle

ps
링크acmicpc.net/…
출처BOJ
문제 번호7694
문제명Triangle
레벨골드 3
분류

Pick's theorem

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

풀이

  • 픽의 정리를 이용해서 삼각형 내부의 격자점의 갯수를 구하는 문제
  • Electric Fence에서 삼각형의 밑변이 x축 위에 있어야 된다는 조건만 빠진 버전이다.

코드

"""Solution code for "BOJ 7694. Triangle".

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

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

import sys
from teflib import geometry


def main():
    while (line := sys.stdin.readline().rstrip()) != '0 0 0 0 0 0':
        x1, y1, x2, y2, x3, y3 = [int(x) for x in line.split()]

        polygon = [(x1, y1), (x2, y2), (x3, y3)]
        interior_points, _ = geometry.lattice_point_in_polygon(polygon)
        print(interior_points)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
B᠎ A J Y Q
 
ps/problems/boj/7694.txt · 마지막으로 수정됨: 2023/04/17 05:42 저자 teferi