#include <fstream>
#include <cstring>
#define oo int(2e9)
 
using namespace std;
 
ifstream fi("bibel.in");
ofstream fo("bibel.out");
int pn, tip, n, i, j;
int conf, sol, Pc[20], Px[20], Py[20], X[20], Y[20], C[132000][17], Cost[20][20];
 
 
int get_dist(int x1, int y1, int x2, int y2)
{
    return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}
 
bool solve()
{
    //stiu ca trebuie sa termin intai nivelul precedent
    n = 0;
    while(fi >> tip)
    {
        if(tip == 1) break;
        if(tip == 2) return 0;
        ++n;
        fi >> X[n] >> Y[n];
    }
    for(i = 1; i <= n; i++)
        for(j = i+1; j <= n; j++)
            Cost[i][j] = Cost[j][i] = get_dist(X[i], Y[i], X[j], Y[j]);
    for(i = 0; i <= (1<<n); i++)
        for(j = 0; j <= n; j++)
            C[i][j] = (oo);
    for(i = 0; i < n; i++)
        for(j = 0; j < pn; j++)
        {
            if(j == 0) C[1<<i][i] = (oo);
            C[1<<i][i] = min(C[1<<i][i], Pc[j] + get_dist(X[i+1], Y[i+1], Px[j+1], Py[j+1]));
        }
    for(conf = 1; conf < (1 << n); conf++)
        for(i = 0; i < n; i++)
        if((1<<i) & conf) //daca exista i in configuratie
        {
            for(j = 0; j < n; j++)
            if(((1<<j)&conf) and i != j) //daca exista j in configuratie
            C[conf][i] = min(C[conf][i], Cost[i+1][j+1] + C[conf^(1<<i)][j]);
        }
    for(sol = (oo) , i = 0, conf = (1<<n) - 1; i < n; i++)
        sol = min(sol, C[conf][i]);
    fo << sol << "\n";
    memcpy(Px, X, sizeof(X));
    memcpy(Py, Y, sizeof(Y));
    for(i = 0; i < n; i++) Pc[i] = C[(1<<n)-1][i];
    pn = n;
    return 1;
}
 
 
 
int main()
{
    pn = 1;
    Pc[0] = 0;
    Px[1] = Py[1] = 0;
    while(solve());
    return 0;
}