Cortes

/*
    Author: [UFC-QXD] Daniel Vitor Pereira Rodrigues <[email protected]>
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
typedef pair<int, int> ii;
typedef pair<i64, i64> ll;
typedef vector<int> vi;
typedef vector<i64> vi64;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<vi> vvi;

const double eps = 1e-9;

#define eq(a, b) (abs(a - b) < eps)
#define lt(a, b) ((a + eps) < b)
#define gt(a, b) (a > (b + eps))
#define le(a, b) (a < (b + eps))
#define ge(a, b) ((a + eps) > b)

struct pt { double x, y; };

double dist(const pt& a, const pt& b) {
    return hypot(a.x-b.x, a.y-b.y);
}

int seen[500][500], timer;
double dp[500][500];

pt pts[500];

int n;
double solve(int i, int j) {
    if (j <= i + 2) return 0.0;
    if (seen[i][j] == timer) return dp[i][j];
    seen[i][j] = timer;
    double ans = 1e12;
    ans = min(ans, solve(i + 1, j - 1) + (i+2<j)*dist(pts[i + 1], pts[j - 1]));
    ans = min(ans, solve(i, j - 2) + (i+2<j)*dist(pts[i], pts[j - 2]));
    ans = min(ans, solve(i + 2, j) + (i+2<j)*dist(pts[i + 2], pts[j]));
    if (i+3<j) {
        ans = min(ans, solve(i, j - 3) + dist(pts[j], pts[j-3]));
        ans = min(ans, solve(i + 3, j) + dist(pts[i], pts[i+3]));
    }
    return dp[i][j] = ans;
}

double ans;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n;
    n <<= 1;

    for (int i = 0; i < n; ++i) {
        cin >> pts[i].x >> pts[i].y;
        pts[i+n] = pts[i];
    }

    ans = 1e12;

    for (int i = 0; i < n; ++i) {
        for (int j = i + 3; j < n; ++j) {
            ++timer;
            ans = min(ans, dist(pts[i], pts[j]) +
                           solve(i, j) + solve(j, i+n));
        }
    }

    cout << fixed << setprecision(4);
    cout << ans << '\n';

    return 0;
}