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

Hướng tiếp cận

Bài toán hỏi diện tích đa giác đơn cho bởi danh sách đỉnh có thứ tự. Công cụ kinh điển là công thức Shoelace (công thức dây giày).

Nhận xét quan trọng

1. Với đa giác đơn $P$ có các đỉnh $(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)$ theo thứ tự (cùng chiều hoặc ngược chiều kim đồng hồ), ta có:

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

   với quy ước $(x_{N+1},y_{N+1})\equiv (x_1,y_1)$.

2. Tổng bên trong có thể âm (nếu các đỉnh liệt kê theo chiều kim đồng hồ). Vì vậy bắt buộc lấy giá trị tuyệt đối.

3. Đề yêu cầu in ra $2S$ chứ không phải $S$ — vì $2S$ luôn là số nguyên còn $S$ có thể là số bán nguyên.

Thuật toán

đọc N
đọc các điểm (x[i], y[i]), i = 0..N-1
s = 0
for i = 0..N-1:
    j = (i + 1) mod N
    s += x[i] * y[j] - x[j] * y[i]
in ra |s|

Độ phức tạp

• Thời gian: $O(N)$.
• Bộ nhớ: $O(N)$ để lưu các đỉnh.

Lưu ý cài đặt

• Với $N\le {10}^5$ và $|x|,|y|\le {10}^6$, mỗi tích $x_i·y_j$ có thể tới ${10}^{12}$, và tổng có thể tới $N·4·{10}^{12}=4·{10}^{17}$ — vượt phạm vi 32-bit. Phải dùng long long.