Vùng Đa Giác Lồi

Buổi 64 — Contest Chặng 7
Points
32
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho N điểm trên mặt phẳng tọa độ. Tìm diện tích bao lồi (convex hull) của tập điểm. In ra diện tích nhân 2 (để tránh số thực).

Dữ liệu vào

Dòng 1: Số nguyên N (3 ≤ N ≤ 10^5) N dòng tiếp theo, mỗi dòng 2 số nguyên x, y (-10^9 ≤ x, y ≤ 10^9)

Dữ liệu ra

Một số nguyên — diện tích bao lồi nhân 2.

Ví dụ
Input Output
4\n0 0\n2 0\n2 2\n0 2 8
Giới hạn
  • 3 ≤ N ≤ 10^5
  • -10^9 ≤ x, y ≤ 10^9
  • Không có 3 điểm nào thẳng hàng (bao lồi có ít nhất 3 đỉnh)
Draft saved