사용자 도구

사이트 도구


ps:teflib:geometry

geometry.py

imports and globals

import bisect
import enum
import itertools
import math
from collections.abc import Callable, Iterable, Sequence
from typing import TypeAlias, Literal

Point: TypeAlias = Sequence[int]
Vector: TypeAlias = Sequence[int]
Polygon: TypeAlias = Sequence[Point]

twice_of_polygon_area

코드

# N twice_of_polygon_area
# I {"version": "0.1"}
def twice_of_polygon_area(polygon: Polygon) -> int:
    """Computes twice of area of given polygon in O(n)."""
    signed_area = sum(
        (p1[0] - p2[0]) * (p1[1] + p2[1])
        for p1, p2 in itertools.pairwise([*polygon, polygon[0]])
    )
    return abs(signed_area)

설명

  • TODO

이 코드를 사용하는 문제

출처문제 번호Page레벨
BOJ18298Icebergs골드 5
BOJ2166다각형의 면적골드 5
BOJ6384Area골드 3

lattice_point_in_polygon

코드

# N lattice_point_in_polygon
# I {"version": "0.1"}
def lattice_point_in_polygon(polygon: Polygon) -> tuple[int, int]:
    """Counts lattice points at boundary and interior of polygon in O(n).

    Args:
        polygon: A simple polygon.
    Returns:
        A tuple of (I, B).
        - I: the number of lattice points lying strictly inside the polygon.
        - B: the number of lattice points lying on polygon sides.
    """
    twice_area = boundary_point_count = 0
    for p1, p2 in itertools.pairwise([*polygon, polygon[0]]):
        twice_area += (p1[0] - p2[0]) * (p1[1] + p2[1])
        boundary_point_count += math.gcd(p1[0] - p2[0], p1[1] - p2[1])
    interior_point_count = (abs(twice_area) - boundary_point_count) // 2 + 1
    return interior_point_count, boundary_point_count

설명

  • TODO

이 코드를 사용하는 문제

출처문제 번호Page레벨
BOJ27123Electric Fence실버 2
BOJ6384Area골드 3
BOJ7694Triangle골드 3

토론

댓글을 입력하세요:
M T H V E
 
ps/teflib/geometry.txt · 마지막으로 수정됨: 2023/04/17 05:46 저자 teferi