Diện Tích Bao Lồi Tập Điểm
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Trên mặt phẳng tọa độ $Oxy$, cho $N$ điểm nguyên có tọa độ $(x_i, y_i)$. Hãy tìm bao lồi nhỏ nhất chứa tất cả $N$ điểm này và in ra hai lần diện tích của đa giác bao lồi đó (nếu tất cả các điểm thẳng hàng hoặc $N < 3$, diện tích bằng $0$).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $N$ ($1 \le N \le 10^5$).
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là hai lần diện tích của bao lồi.
Ví dụ
| Input | Output |
|---|---|
| 5 0 0 4 0 4 3 0 3 2 1 |
24 |
Giới hạn
- $1 \le N \le 10^5$
- $|x_i|, |y_i| \le 10^9$
Community Discussion