Chu vi bao lồi

Cho $N$ điểm trên mặt phẳng tọa độ với tọa độ nguyên. Bao lồi của tập điểm là đa giác lồi nhỏ nhất chứa toàn bộ $N$ điểm. Hãy tính chu vi của bao lồi đó.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $N$ — số điểm.
• $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$ và $y_i$.

Dữ liệu ra

Một số thực duy nhất — chu vi bao lồi, in với ít nhất 6 chữ số sau dấu phẩy. Sai số tuyệt đối hoặc tương đối ${10}^{-4}$ được chấp nhận.

Trường hợp suy biến:

• Nếu $N=1$: chu vi bằng $0$.
• Nếu tất cả các điểm thẳng hàng (bao lồi suy biến thành đoạn thẳng): chu vi bằng hai lần độ dài đoạn thẳng nối hai điểm xa nhau nhất trên đường thẳng đó.

Ràng buộc

• $1\le N\le {10}^5$.
• $-{10}^6\le x_i,y_i\le {10}^6$.
• Các điểm có thể trùng nhau.

Ví dụ

Ghi chú

Sử dụng kiểu double (hoặc long double) khi cộng các cạnh; phần tính bao lồi nên giữ ở số nguyên (cross product là số nguyên) để tránh sai số.