Đường đi lồi dài nhất

Cho một đa giác lồi chặt với $n$ đỉnh (không có ba đỉnh nào thẳng hàng). Các đỉnh được cho theo thứ tự chiều kim đồng hồ.

Bạn cần chọn một đường đi trên tập đỉnh của đa giác, thăm mỗi đỉnh nhiều nhất một lần. Đường đi là một dãy các đỉnh phân biệt; nối hai đỉnh liên tiếp trong dãy bằng một đoạn thẳng. Yêu cầu: các đoạn thẳng này không được cắt hay chạm nhau, ngoại trừ tại các đỉnh chung trong dãy.

Hãy tìm độ dài lớn nhất của một đường đi thỏa mãn điều kiện trên (tổng độ dài các đoạn thẳng).

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số đỉnh.
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i,y_i$ là tọa độ đỉnh thứ $i$.

Dữ liệu ra

In ra một số thực là độ dài lớn nhất của đường đi không tự cắt.

Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với đáp án chuẩn không vượt quá ${10}^{-9}$.

Ràng buộc

• $2\le n\le 2500$
• $|x_i|,|y_i|\le {10}^9$
• Đa giác lồi chặt, không có ba đỉnh thẳng hàng, các đỉnh cho theo chiều kim đồng hồ.

Ví dụ