====== geometry.py ======

===== imports and globals =====
<dkpr py>
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]
</dkpr>


===== twice_of_polygon_area =====

==== 코드 ====
<dkpr py>
# 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)
</dkpr>

==== 설명 ====
  * TODO

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[geometry.twice_of_polygon_area]*
csv: 0
----

===== lattice_point_in_polygon =====

==== 코드 ====
<dkpr py>
# 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
</dkpr>

==== 설명 ====
  * TODO

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[geometry.lattice_point_in_polygon]*
csv: 0
----