Điểm Nguyên Trong Đa Giác

Buổi 61 — Hình học tính toán
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho một đa giác đơn gồm $N$ đỉnh có tọa độ nguyên. Hãy đếm số lượng điểm có tọa độ nguyên (lattice points) nằm hoàn toàn bên trong đa giác và số lượng điểm nguyên nằm trên biên của đa giác.

Gợi ý: Kết hợp công thức Shoelace, thuật toán Euclid ($\gcd$) và định lý Pick.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($3 \le N \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ ($|x_i|, |y_i| \le 10^9$) là tọa độ đỉnh thứ $i$.
Dữ liệu ra
  • In ra hai số nguyên cách nhau bởi dấu cách: số điểm nguyên nằm hoàn toàn bên trong đa giác và số điểm nguyên nằm trên biên đa giác.
Ví dụ
Input Output
4
0 0
4 0
4 4
0 4
9 16
Giới hạn
  • $3 \le N \le 10^5$
  • $|x_i|, |y_i| \le 10^9$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved