Vùng Đa Giác Lồi
Points
32
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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)
Community Discussion