Diện Tích Bao Lồi Tập Điểm

Buổi 75-76 — Stress Test
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved