📖 Bài giảng & lời giải: đây là Bài tập 5 trong bài giảng Chuyên đề nâng cao 1: Hình học tính toán trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Khu vườn có dạng một đa giác đơn (các cạnh không cắt nhau, trừ hai cạnh kề nhau chung một đỉnh) gồm $n$ đỉnh có toạ độ nguyên. Người ta trồng một cây tại mọi điểm có toạ độ nguyên nằm trên hàng rào (biên của đa giác) hoặc nằm bên trong khu vườn. Hãy cho biết có bao nhiêu cây trên hàng rào và bao nhiêu cây nằm hẳn bên trong.

Dữ liệu vào

• Dòng 1: số nguyên $n$ ($3 \le n \le 10^5$).
• $n$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $x, y$ ($|x|, |y| \le 10^6$) là toạ độ một đỉnh, liệt kê lần lượt dọc theo biên (theo chiều bất kỳ). Có thể có ba đỉnh liên tiếp thẳng hàng. Dữ liệu đảm bảo diện tích đa giác dương.

Kết quả

In ra hai số nguyên cách nhau một dấu cách: số điểm nguyên trên biên và số điểm nguyên nằm hẳn bên trong đa giác.

Sample Input

5
1 1
6 0
7 4
3 6
0 3

Sample Output

8 24