Một đa giác đơn có \(N\) đỉnh được vẽ trên một lưới ô vuông vô hạn. Trong đa giác này, chỉ hai cạnh kề nhau mới tiếp xúc tại đỉnh chung; mọi cặp cạnh khác không cắt nhau và cũng không tiếp xúc. Tất cả các đỉnh nằm tại các điểm lưới, tức là có tọa độ nguyên.

Hãy tính tổng độ dài các đoạn thuộc những đường lưới nằm hoàn toàn bên trong đa giác, không tính phần nằm trên biên. Những đoạn cần tính được tô đậm trong các hình ví dụ.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), là số đỉnh của đa giác.

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\), là tọa độ một đỉnh. Các đỉnh được cho theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Mọi đỉnh đều phân biệt, nhưng có thể có hơn hai đỉnh liên tiếp cùng nằm trên một đường thẳng.

Dữ liệu ra

In một số thập phân duy nhất: tổng độ dài các đoạn thuộc đường lưới nằm hoàn toàn bên trong đa giác.

Gọi kết quả bạn in là \(L\) và đáp án là \(R\). Kết quả được chấp nhận nếu thỏa mãn ít nhất một trong hai điều kiện:

• Sai số tương đối:

  \[ |L-R|\le R\cdot10^{-6}. \]

• Sai số tuyệt đối:

  \[ |L-R|\le10^{-6}. \]

Ràng buộc

• \(3 \le N \le 100\,000\).
• \(-500\,000\,000 \le x,y \le 500\,000\,000\).

Phân nhóm

• Trong các bộ dữ liệu có tổng cộng 50 điểm, tất cả các cạnh của đa giác nằm trên các đường lưới.
• 50 điểm còn lại không có ràng buộc bổ sung.

Ví dụ

3
5 1
2 4
1 1

10.0

5
0 0
-2 2
-2 -1
2 -2
2 0

12.5