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

Cho một đa giác đơn (simple polygon) gồm $N$ đỉnh có toạ độ nguyên, được liệt kê theo thứ tự dọc theo biên (cùng chiều kim đồng hồ hoặc ngược chiều kim đồng hồ). Đa giác đơn nghĩa là các cạnh không tự cắt nhau (ngoại trừ tại các đỉnh chung kề nhau).

Hãy đếm số điểm nguyên (điểm có cả hai toạ độ là số nguyên) nằm bên trong nghiêm ngặt đa giác — tức là không nằm trên biên của đa giác.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$ — số đỉnh.
• $N$ dòng sau, mỗi dòng chứa hai số nguyên $x_i,y_i$ — toạ độ đỉnh thứ $i$.

Dữ liệu ra

In ra một số nguyên duy nhất — số điểm nguyên nằm bên trong nghiêm ngặt đa giác.

Ràng buộc

• $3\le N\le {10}^5$.
• $|x_i|,|y_i|\le {10}^6$.
• Đa giác đảm bảo là đa giác đơn; không có hai đỉnh liên tiếp trùng nhau.
• Kết quả có thể tới $~4·{10}^{12}$, nên cần dùng kiểu số nguyên 64-bit.

Ví dụ

Ghi chú

Có thể dùng định lý Pick: với đa giác đơn có các đỉnh nguyên, $A=I+B/2-1$, trong đó $A$ là diện tích, $I$ là số điểm nguyên bên trong, $B$ là số điểm nguyên trên biên.