TSP Solution #2

import java.io.*;
import java.util.*;
import java.math.*;
import java.awt.geom.*;

public class Solution implements Runnable {

    public static void main(String[] args) throws Exception {
        new Thread(null, new Solution(), "", 1 << 26).start();
    }

    BufferedReader in;
    PrintWriter out;
    StringTokenizer st;

    final String fname = "";

    private String next() throws Exception {
        if (st == null || !st.hasMoreElements())
            st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }

    private int nextInt() throws Exception {
        return Integer.parseInt(next());
    }

    private long nextLong() throws Exception {
        return Long.parseLong(next());
    }

    private double nextDouble() throws Exception {
        return Double.parseDouble(next());
    }

    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
            solve();
        } catch (Exception ex) {
            throw new RuntimeException(ex);
        } finally {
            out.close();
        }
    }

    static final double EPS = 1e-14;

    class Point implements Comparable<Point> {
        double x,y;
        int index;

        public Point(double x, double y, int index) {
            this.x = x;
            this.y = y;
            this.index = index;
        }

        @Override
        public int compareTo(Point o) {
            if (this.x < o.x) return -1;
            if (this.x > o.x) return 1;
            if (this.y < o.y) return -1;
            if (this.y > o.y) return 1;
            return 0;
        }

    }

    double distance (Point a, Point b) {
        return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    }

    boolean cw (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;
    }

    boolean ccw (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;
    }


    ArrayList<Point> stupidAlgo (ArrayList<Point> a) {
        int n = a.size();
        double d [][] = new double [n][1<<n];
        int preMask [][] = new int [n][1<<n];
        int preVertex [][] = new int [n][1<<n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(d [i], 1e3);
            Arrays.fill(preVertex[i], -1);
        }
        for (int i = 0; i < n; i++)
            d[i][(1<<i)] = 0.0;
        for (int mask = 1; mask < (1<<n); mask++) {
            for (int i = 0; i < n; i++) {
                if (((1<<i) & mask)>0) { // last
                    for (int j = 0; j < n; j++)
                        if (((1<<j) & mask)==0) { //next
                            double dist = distance (a.get(i), a.get(j));
                            int nextmask = (1<<j) | mask;
                            if (d[j][nextmask] > d[i][mask] + dist) {
                                d[j][nextmask] = d[i][mask] + dist;
                                preMask[j][nextmask] = mask;
                                preVertex[j][nextmask] = i;
                            }
                        }
                }
            }
        }
        int bestmask = (1<<n) - 1;
        int besti = 17;
        ArrayList<Point> ret = new ArrayList<Solution.Point> ();
        ret.add(a.get(besti));
        //restore
        while (true) {
            int prevmask = preMask[besti][bestmask];
            int previ = preVertex[besti][bestmask];
            if (previ == -1) break;
            ret.add(a.get(previ));
            besti = previ;
            bestmask = prevmask;
        }
        return ret;
    }

    ArrayList<Point> convexHull (ArrayList<Point> a) {
        Collections.sort(a);
        Point p1 = a.get(0);
        Point p2 = a.get(a.size() - 1);
        ArrayList<Point> up = new ArrayList<Solution.Point>();
        ArrayList<Point> down = new ArrayList<Solution.Point>();
        up.add(p1);
        down.add(p1);
        for (int i = 1; i < a.size(); i++) {
            if (i == a.size() - 1 || cw (p1, a.get(i), p2)) {
                while (up.size() >= 2 && !cw (up.get(up.size() - 2), up.get(up.size() - 1), a.get(i)))
                    up.remove(up.size() - 1);
                up.add(a.get(i));
            }
            if (i == a.size() - 1 || ccw (p1, a.get(i), p2)) {
                while (down.size() >= 2 && !ccw (down.get(down.size() - 2), down.get(down.size() - 1), a.get(i)))
                    down.remove(down.size() - 1);
                down.add(a.get(i));

            }
        }
        ArrayList<Point> result = new ArrayList<Solution.Point>();
        for (int i = 0; i < up.size(); i++)
            result.add(up.get(i));
        for (int i = down.size() - 2; i > 0; i--)
            result.add(down.get(i));
        return result;
    }

    void reverse (ArrayList<Point> a) {
        for (int i = 0; i < a.size()/2; i++) {
            Point temp = a.get(i);
            a.set(i, a.get(a.size() - i - 1));
            a.set(a.size() - i - 1, temp);
        }
    }

    public void solve() throws Exception {
        int n = nextInt();
        ArrayList<Point> a = new ArrayList<Solution.Point>();
        for (int i = 0; i < n; i++) {
            a.add(new Point(nextDouble(), nextDouble(), i));
        }
        ArrayList<Point> convex = convexHull (a);

        for (Point p : convex) {
            for (int i = 0; i < a.size(); i++) {
                if (a.get(i).index == p.index) {
                    a.remove(i);
                    break;
                }
            }
        }

        int m = convex.size();

        int count = 0;

        ArrayList<Point> ret = new ArrayList<Solution.Point>();

        for (int k = 0; k < n - m; k++) {
            if (n - m - count == 20) {
                double bestDist = 1e3;
                int besti = -1;
                int bestj = -1;
                ArrayList<Point> stupid = stupidAlgo (a);
                reverse (stupid);
                for (int i = 0; i < convex.size(); i++) {
                    int ii = (i + 1) % convex.size();
                    for (int j = 0; j < stupid.size(); j++) {
                        int jj = (j + 1) % stupid.size();
                        double dist1 = distance(convex.get(i), stupid.get(j));
                        double dist2 = distance(convex.get(ii), stupid.get(jj));
                        double dist3 = distance(convex.get(i), convex.get(ii));
                        double dist4 = distance(stupid.get(j), stupid.get(jj));
                        double dist = dist1 + dist2 - dist3 - dist4;
                        if (dist < bestDist) {
                            bestDist = dist;
                            besti = i;
                            bestj = j;
                        }
                    }
                }
                for (int i = 0; i <= besti; i++)
                    ret.add(convex.get(i));
                for (int i = bestj; i >= 0; i--)
                    ret.add(stupid.get(i));
                for (int i = stupid.size() - 1; i >= bestj + 1; i--)
                    ret.add(stupid.get(i));
                for (int i = besti + 1; i < convex.size(); i++)
                    ret.add(convex.get(i));
                break;
            }
            int besti = -1;
            int bestj = -1;
            double bestDist = 1e9;
            for (int i = 0; i < a.size(); i++) {
                double px = a.get(i).x;
                double py = a.get(i).y;
                for (int j = 0; j < convex.size(); j++) {
                    int jj = (j + 1) % convex.size();
                    double x1 = convex.get(j).x;
                    double y1 = convex.get(j).y;
                    double x2 = convex.get(jj).x;
                    double y2 = convex.get(jj).y;
                    double dist = Line2D.ptSegDist(x1, y1, x2, y2, px, py);
                    if (dist < bestDist) {
                        bestDist = dist;
                        besti = i;
                        bestj = jj;
                    }
                }
            }
            convex.add(bestj, a.get(besti));
            a.remove(besti);
            count ++;
        }

        double result = 0.0;
        for (int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            result += distance (ret.get(i), ret.get(j));
        }

        out.printf("%.14f\n", result);
        for (int i = 0; i < n; i++) {
            out.print(ret.get(i).index + " ");
        }

    }


}