Diện tích đa giác đơn

Cho một đa giác đơn (các cạnh không cắt nhau, ngoài việc dùng chung đầu mút liền kề) có $N$ đỉnh, được liệt kê theo thứ tự dọc theo chu vi (có thể cùng chiều kim đồng hồ hoặc ngược chiều kim đồng hồ). Các đỉnh có tọa độ nguyên.

Hãy tính hai lần diện tích của đa giác. Kết quả luôn là một số nguyên không âm.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $N$ — số đỉnh của đa giác.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$ và $y_i$ — tọa độ đỉnh thứ $i$.

Dữ liệu ra

Một số nguyên duy nhất là hai lần diện tích của đa giác.

Ràng buộc

• $3\le N\le {10}^5$.
• $|x_i|,|y_i|\le {10}^6$.
• Đa giác là đa giác đơn (không tự cắt).
• Không có ba đỉnh liên tiếp thẳng hàng và đa giác có diện tích thực sự dương.

Ví dụ

Ghi chú

Sử dụng công thức Shoelace (dây giày):

$$2·S=|{\sum }_{i=1}^N(x_i·y_{i+1}-x_{i+1}·y_i)|$$

trong đó các chỉ số tính theo chu trình (đỉnh sau đỉnh $N$ là đỉnh $1$).

Hãy chú ý kiểu dữ liệu: với $N,|x|,|y|$ ở mức tối đa, tổng có thể vượt phạm vi 32-bit.