trang chủ / đề bài / geomint / lời giải

Đếm điểm nguyên trong đa giác

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả:

huunguyen

Hướng tiếp cận

Định lý Pick cho đa giác đơn có đỉnh nguyên:

$A = I + \frac{B}{2} - 1 ⟹ I = A - \frac{B}{2} + 1 .$

Nhận xét quan trọng

Diện tích qua Shoelace: $2 A = | \sum (x_{i} y_{i + 1} - x_{i + 1} y_{i}) |$ .
Số điểm nguyên trên cạnh $(x_{1}, y_{1}) \to (x_{2}, y_{2})$ (không tính một đầu mút) = $gcd (| x_{2} - x_{1} |, | y_{2} - y_{1} |)$ . Tổng: $B = \sum_{i} gcd (| x_{i + 1} - x_{i} |, | y_{i + 1} - y_{i} |)$ .
$I = (2 A - B) / 2 + 1$ . $2 A$ và $B$ luôn cùng tính chẵn lẻ ⇒ chia 2 chính xác.

Độ phức tạp

Thời gian: $O (N \log V)$ .
Bộ nhớ: $O (N)$ .

Bình luận

Không có bình luận tại thời điểm này.