Cho n điểm nguyên trên mặt phẳng. Dựng bao lồi bằng thuật toán Andrew (monotone chain), chỉ giữ các đỉnh thực sự (không giữ điểm thẳng hàng trên cạnh). In hai số: số đỉnh của bao lồi và hai lần diện tích của nó (luôn là số nguyên).
Nếu mọi điểm trùng nhau hoặc chỉ có một điểm phân biệt, diện tích là 0.
Dòng đầu: n. n dòng sau: mỗi dòng hai số nguyên x, y.
1≤n≤2⋅105, ∣x∣,∣y∣≤109.
Một dòng: số đỉnh bao lồi và 2× diện tích, cách nhau bởi dấu cách.
Ví dụ:
Đầu vào:
4
0 0
4 0
4 4
0 4
Đầu ra:
4 32
Giải thích:
Đang tải editor...