Salesman

#include <iostream>
#include <memory.h>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>

#define sqr(x) ((x) * (x))

const int N = 15;
const double INF = 1e100;

double d[N][N];
int n, k, path_len, path[N];
double record = INF, dist[N];
bool used[N], alive[N];

struct Point {
    double x, y;
    int hull_index;

    Point() : x(0.), y(0.), hull_index(0) {
    }

    bool operator < (const Point &q) const {
        if (hull_index == q.hull_index) {
            return x < q.x || x == q.x && y < q.y;
        } else {
            return hull_index < q.hull_index;
        }
    }

    double dist(const Point &q) const {
        return sqrt(sqr(x - q.x) + sqr(y - q.y));
    }

} points[N], hull_points[N];

bool clock_wise(Point &a, Point &b, Point &c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

bool counter_clock_wise(Point &a, Point &b, Point &c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

std::istream& operator>>(std::istream &is, Point &p) {
    is >> p.x >> p.y;
    return is;
}

std::vector<int> build_convex_hull() {
    std::sort(points, points + n);
    Point p1 = points[0], p2 = points[n - 1];
    std::vector<int> up, down, result;
    up.push_back(0);
    down.push_back(0);
    for (size_t i = 1; i < n; ++i) {
        if (i == n - 1 || clock_wise(p1, points[i], p2)) {
            while (up.size() >= 2 && !clock_wise(points[up[up.size()-2]], points[up[up.size()-1]], points[i]))
                up.pop_back();
            up.push_back(i);
        }
        if (i == n - 1 || counter_clock_wise(p1, points[i], p2)) {
            while (down.size() >= 2 && !counter_clock_wise(points[down[down.size()-2]], points[down[down.size()-1]], points[i]))
                down.pop_back();
            down.push_back(i);
        }
    }
    for (size_t i = 0; i < up.size(); ++i) {
        result.push_back(up[i]);
    }
    for (size_t i = down.size()-2; i > 0; --i) {
        result.push_back(down[i]);
    }
    return result;
}

void input() {
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> points[i];
    }
}

void precalculate_distances() {
    for (int i = 0; i < n + k; ++i) {
        for (int j = 0; j < n + k; ++j) {
            d[i][j] = points[i].dist(points[j]);
        }
    }
}

void preprocess() {
    std::vector<int> hull_indicies = build_convex_hull();
    for (size_t i = 0; i < hull_indicies.size(); ++i) {
        points[hull_indicies[i]].hull_index = i + 1;
    }
    std::sort(points, points + n);
    for (int i = 0; i < n; ++i) {
        if (points[i].hull_index) {
            hull_points[k++] = points[i];
        }
    }
    n -= k;
    precalculate_distances();
}

inline double area(const Point &a, const Point &b, const Point &c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline bool intersect(double a, double b, double c, double d) {
    if (a > b) {
        std::swap(a, b);
    }
    if (c > d) {
        std::swap(c, d);
    }
    return std::max(a, c) <= std::min(b, d);
}

bool segment_intersect(const Point &a, const Point &b, const Point &c, const Point &d) {
    return intersect(a.x, b.x, c.x, d.x)
        && intersect(a.y, b.y, c.y, d.y)
        && area(a, b, c) * area(a, b, d) <= 1e-8
        && area(c, d, a) * area(c, d, b) <= 1e-8;
}

bool check_intersections(int v) {
    for (int i = 1; i < path_len - 1; ++i) {
        if (segment_intersect(points[path[i - 1]], points[path[i]], points[path[path_len - 1]], points[v])) {
            return false;
        }
    }
    return true;
}

double mst_solution() {
    memset(alive, 0, sizeof(alive));
    for (int i = 0; i < n + k; ++i) {
        dist[i] = INF;
    }
    int s = -1;
    for (int i = 0; i < n + k && s < 0; ++i) {
        if (!used[i]) {
            s = i;
            dist[s] = 0;
        }
    }
    double result = 0;
    while (true) {
        int num = -1;
        for (int i = 0; i < n + k; ++i) {
            if (!used[i] && !alive[i] && (num == -1 || dist[i] < dist[num])) {
                num = i;
            }
        }
        if (num == -1) {
            break;
        }
        result += dist[num];
        alive[num] = true;
        for (int i = 0; i < n + k; ++i) {
            dist[i] = std::min(dist[i], d[num][i]);
        }
    }
    return result;
}

void brut(int v, int used_from_hull, int used_not_from_hull, double dist) {
    if (dist >= record || dist + mst_solution() >= record) {
        return;
    }
    if (used_from_hull + used_not_from_hull == n + k) {
        record = std::min(record, dist + d[v][n]);
        return;
    }
    used[v] = true;
    path[path_len++] = v;
    if (used_from_hull < k) {
        int to = n + used_from_hull;
        if (check_intersections(to)) {
            brut(to, used_from_hull + 1, used_not_from_hull, dist + d[v][to]);
        }
    }
    if (used_not_from_hull < n) {
        for (int i = 0; i < n; ++i) {
            if (!used[i] && check_intersections(i)) {
                brut(i, used_from_hull, used_not_from_hull + 1, dist + d[v][i]);
            }
        }
    }
    used[v] = false;
    --path_len;
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    clock_t begin = clock();
    input();
    preprocess();
    record = 2 * mst_solution();
    brut(n, 1, 0, 0);
    std::cout << record << std::endl;
    std::cerr << (clock() - begin) * 1. / CLOCKS_PER_SEC << std::endl;
    return 0;
}