Hàng Rào Bao Quanh Đảo

Buổi 61 — Hình học tính toán
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Trên một hòn đảo nhỏ có $N$ cây cổ thụ quý hiếm. Để bảo vệ chúng, kiểm lâm muốn dựng một hàng rào khép kín có tổng độ dài nhỏ nhất bao quanh tất cả $N$ cây (các cây có thể nằm trên hoặc bên trong hàng rào).

Hãy tính chu vi của bao lồi nhỏ nhất chứa tất cả $N$ điểm đã cho. Nếu chỉ có $1$ cây, chu vi bằng $0$. Nếu các cây thẳng hàng, hàng rào đi từ đầu mút này đến đầu mút kia rồi quay lại (tức gấp đôi độ dài đoạn thẳng).

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $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$ ($|x_i|, |y_i| \le 10^9$).
Dữ liệu ra
  • In ra một số thực là chu vi nhỏ nhất cần tìm, làm tròn đến $6$ chữ số thập phân.
Ví dụ
Input Output
5
0 0
4 0
4 3
0 3
2 1
14.000000
Giới hạn
  • $1 \le N \le 10^5$
  • $|x_i|, |y_i| \le 10^9$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved