#include <bits/stdc++.h>
#define maxN 19
#define maxP (1 << 17) + 2
#define mp make_pair
#define pii pair < int, int >
#define f first
#define s second
#define inf 1000000000
using namespace std;
int t, n, m, all, ans, s, dp[maxN][maxP], path[maxN], a[maxN][maxN];
vector < pii > V[maxN];
struct coord
{
    int x, y;
} v[maxN], w[maxN];
void solve();
void write();
void read()
{
    int x = 0;
    n = 0;
    while (1)
    {
        scanf("%d", &x);
        if (x == 2)
            exit(0);
        if (x == 1)
        {
            ++ t;
            break;
        }
        scanf("%d %d", &v[n].x, &v[n].y);
        ++ n;
    }
    if (t == 1)
        ++ n;

    solve();
    write();
    read();
}
int Cost(int x, int conf)
{
    int i, nod;
    if (dp[x][conf] != -1)
        return dp[x][conf];
    dp[x][conf] = inf;
    for (nod = 0; nod < n; ++ nod)
        if (conf & (1 << nod) && nod != x)
        {
            if (nod == 0 && conf != (1 << x) + 1)
                continue;
            if (dp[x][conf] > Cost(nod, conf ^ (1 << x)) + a[x][nod])
                dp[x][conf] = dp[nod][conf ^ (1 << x)] + a[x][nod];
        }
    return dp[x][conf];
}
void init()
{
    all = (1 << n) - 1;
    memset(dp, -1, sizeof(dp));
    dp[0][1] = 0;
    ans = inf;
    int i, j;
    for (i = 0; i < n - 1; ++ i)
        for (j = i + 1; j < n; ++ j)
            a[i][j] = a[j][i] = (v[i].x - v[j].x) * (v[i].x - v[j].x) + (v[i].y - v[j].y) * (v[i].y - v[j].y);
}
int dist(coord a, coord b)
{
    return (a.x - b.x) * (a.x - b.x) - (a.y - b.y) * (a.y - b.y);
}
int mod(int x)
{
    if (x >= 0)
        return x;
    return x + n;
}
void add()
{
    int i, j, d = inf;
    for (j = 0; j < n; ++ j)
        for (i = 0; i < m; ++ i)
            d = min(d, dist(w[path[i]], v[j]) - dist(w[path[mod(i - 1)]], w[path[i]]));
    ans += d;
}
void solve()
{
    int i, j, p, val = 0;
    init();
    for (i = 1; i < n; ++ i)
        if (Cost(i, all) + a[0][i] < ans)
        {
            ans = dp[i][all] + a[0][i];
            p = i;
        }

    if (t != 1)
        add();
    i = 1;
    path[1] = p;
    while (i < n - 1)
    {
        for (j = 0; j < n; ++ j)
            if (path[i] != j && Cost(j, all ^ (1 << path[i])) + a[path[i]][j] == dp[path[i]][all])
            {
                all ^= (1 << path[i]);
                path[++ i] = j;
                break;
            }
        if (a[path[i]][path[i - 1]] > val)
            val = a[path[i]][path[i - 1]];
    }
    if (t != 1)
        val = 0;
    s += ans;
    ans = s - val;
    memcpy(w, v, sizeof(v));
    m = n;
}
void write()
{
    printf("%d\n", ans);
}
int main()
{
    freopen("bibel.in", "r", stdin);
    freopen("bibel.out", "w", stdout);
    read();
    return 0;
}