# 테페리넷

### 사이트 도구

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 - p2) * (p1 + p2)
for p1, p2 in itertools.pairwise([*polygon, polygon])
)
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]):
twice_area += (p1 - p2) * (p1 + p2)
boundary_point_count += math.gcd(p1 - p2, p1 - p2)
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

## 토론

댓글을 입력하세요:
C P I A J

ps/teflib/geometry.txt · 마지막으로 수정됨: 2023/04/17 05:46 저자 teferi 