#include <iostream>
#include <fstream>
#include <vector>
//#include <bits/stdc++.h>
#define in fin
#define out fout
#define mkp make_pair

using namespace std;

ifstream fin("bibel.in");
ofstream fout("bibel.out");

int dp[20][(1 << 20)];

int d( pair<int, int> a, pair<int, int> b ){
    return abs( a.first - b.first ) * abs( a.first - b.first ) + 
            abs( a.second - b.second ) * abs( a.second - b.second );
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int op;
    int cnt = 0;
    int nrbL = 0; // last nr of bile
    vector< pair<int, int> > vL;
    while(true){
        vector< pair<int, int> > v;
        bool stop = 0;
        while(true){
            in >> op;
            if(op == 2){
                stop = 1;
                break;
            }
            if(op == 1) break;
            int l, r; in >> l >> r;
            v.push_back( mkp(l, r) );
        }

        if(stop) break;

        if(cnt == 0){ // primul nivel
            for(int i = 0; i < v.size(); i++){
                for(int j = 0; j < (1 << v.size()); j++){
                    dp[i][j] = 10000000;
                }
            }
            for(int i = 0; i < 17; i++){
                dp[i][ (1 << i) ] = d( mkp(0, 0) , v[i] );
            }
        }else{
            int ll[20]; // ultima linie de dp[j][1..1] de la ult nivel
            for(int i = 0; i < 20; i++){                                        
                ll[i] = dp[i][ (1 << nrbL) - 1 ];
            }

            for(int i = 0; i < v.size(); i++){
                for(int j = 0; j < (1 << v.size()); j++){
                    dp[i][j] = 10000000;
                }
            }
            
            for(int i = 0; i < v.size(); i++){
                for(int j = 0; j < vL.size(); j++){
                    dp[i][ (1 << i) ] = min(dp[i][ (1 << i) ], ll[j] + d(v[i], vL[j]));
                }
            }
        }

        vL = v;
        nrbL = v.size();
        cnt++;


        for(int mask = 0; mask < (1 << v.size()); mask++){
            for(int i = 0; i < v.size(); i++){
                if( (mask & (1 << i)) == 0 ) continue;
                for(int j = 0; j < v.size(); j++){
                    if( (mask & (1 << j)) == 0 ) continue;
                    dp[i][mask] = min(dp[i][mask], dp[j][mask - (1 << i)] + d(v[i], v[j]));
                }
            }
        }

        int mini = dp[0][ (1 << v.size()) - 1 ];
        for(int i = 1; i < v.size(); i++){
            mini = min(mini, dp[i][(1 << v.size()) - 1]);
        }
        out << mini << '\n';
    }

    return 0;
}