#include<stdio.h>

#define maxn 17
#define INF (1<<30)

FILE*f=fopen("bibel.in","r");
FILE*g=fopen("bibel.out","w");

int n,op,i,j,conf,nod,p,ant[maxn];
int x[2][maxn],y[2][maxn],N[2];
int D[maxn][(1<<maxn)+5],dist[maxn][maxn];

inline int distanta ( int x1 , int y1 , int x2 , int y2 ){
	int d = 1LL*(x2-x1)*(x2-x1) + 1LL*(y2-y1)*(y2-y1);
	return d;
}

inline int min ( int a , int b ){
	return a <= b ? a : b;
}

int main () {
	
	p = 0; N[1] = 1;
	for ( ; ; ){
		
		for ( n = 1 ; ; ++n ){
			fscanf(f,"%d",&op);
			if ( op )	break ;
			fscanf(f,"%d %d",&x[p][n-1],&y[p][n-1]);
		}
		
		if ( op == 2 )	break ;
		
		--n;
		
		for ( i = 0 ; i < n - 1 ; ++i ){
			for ( j = i + 1 ; j < n ; ++j ){
				dist[i][j] = dist[j][i] = distanta(x[p][i],y[p][i],x[p][j],y[p][j]);
			}
		}
		
		for ( i = 0 ; i < n ; ++i ){
			for ( j = 0 ; j < (1<<n) ; ++j ){
				D[i][j] = INF;
			}
		}
		
		for ( i = 0 ; i < n ; ++i ){
			for ( j = 0 ; j < N[!p] ; ++j ){
				D[i][1<<i] = min(D[i][1<<i],ant[j]+distanta(x[p][i],y[p][i],x[!p][j],y[!p][j]));
			}
		}
		
		for ( conf = 1 ; conf < (1<<n) ; ++conf ){
			for ( nod = 0 ; nod < n ; ++nod ){
				
				if ( conf & (1<<nod) ){
					
					for ( i = 0 ; i < n ; ++i ){
						if ( i == nod )	continue ;
						
						D[nod][conf] = min(D[nod][conf],D[i][conf-(1<<nod)] + dist[nod][i]);
					}
				}
			}
		}
		
		int sol = INF;
		
		for ( i = 0 ; i < n ; ++i ){
			sol = min(sol,D[i][(1<<n)-1]);
			ant[i] = D[i][(1<<n)-1];
		}
		
		N[p] = n; p = !p;
		
		fprintf(g,"%d\n",sol);
	}
	
	
	fclose(f);
	fclose(g);
	
	return 0;
}