Điểm Nguyên Trong Đa Giác
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề 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
Community Discussion