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

using namespace std;

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

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

ll d( pair<ll, ll> a, pair<ll, ll> 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<ll, ll> > vL;
    while(true){
        vector< pair<ll, ll> > v;
        bool stop = 0;
        while(true){
            in >> op;
            if(op == 2){
                stop = 1;
                break;
            }
            if(op == 1) break;
            ll 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] = 100000000000;
                }
            }
            for(int i = 0; i < 17; i++){
                dp[i][ (1 << i) ] = d( mkp(0, 0) , v[i] );
            }
        }else{
            int llt[20]; // ultima linie de dp[j][1..1] de la ult nivel
            for(int i = 0; i < 20; i++){                                        
                llt[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] = 100000000000;
                }
            }
            
            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) ], llt[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]));
                }
            }
        }

        ll 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;
}