#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;	
ifstream in("bibel.in");
ofstream out("bibel.out");
int cost[20][20],dp[(1<<18)+2][18];
pair<int,int> p[20];
vector<pair<int,pair<int,int > > > st;
long long S=0;
int dist(pair<int,int> a,pair<int,int> b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int main()
{
    int n=0,i,j,nr;
    st.push_back({0,{0,0}});
    while(1)
    {
        in>>nr;
        if(nr==2) break;
        if(nr==1)
        {
            for(i=1;i<(1<<n);i++)
                for(j=0;j<n;j++)
                    dp[i][j]=1<<28;
            for(j=st.size()-1;j>=0;j--)
            {
                for(i=0;i<n;i++)
                    dp[1<<i][i]=min(dp[1<<i][i],st[j].x+dist(st[j].y,p[i]));
                st.pop_back();
            }
            for(i=1;i<(1<<n);i++)
                for(j=0;j<n;j++)
                    if(i&(1<<j))
                        for(nr=0;nr<n;nr++)
                            if(nr!=j&&(i&(1<<nr)))
                                dp[i][nr]=min(dp[i][nr],dp[i^(1<<nr)][j]+cost[j][nr]);
            for(i=0,nr=1<<28;i<n;i++)
                nr=min(nr,dp[(1<<n)-1][i]);
            for(i=0;i<n;i++)
                st.push_back({dp[(1<<n)-1][i]-nr,p[i]});
            S+=1LL*nr;
            out<<S<<"\n";
            n=0;
            continue;
        }
        in>>p[n].x>>p[n].y;
        for(i=0;i<n;i++)
            cost[i][n]=cost[n][i]=dist(p[i],p[n]);
        n++;
    }
    return 0;
}