#include #include #include #include #include #include #include using namespace std; using uint = unsigned int; using ll = long long; #define CIN( LL , A ) LL A; cin >> A #define GETLINE( A ) string A; getline( cin , A ) #define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) #define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR_LL( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0 #define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << endl; return 0 #define MIN( A , B ) A < B ? A : B; #define MAX( A , B ) A < B ? B : A; template inline T Distance( const T& a , const T& b ){ return a < b ? b - a : a - b; } #define SetAB( x , y ) \ \ a[num] = x; \ b[num] = y; \ ll p_num = ( x / W ) + ( y / H ) * Px; \ p[num] = p_num; \ ll& m_size_p_num = m_size[p_num]; \ m[p_num][m_size_p_num] = num; \ m_size_p_num++; \ \ #define SetNear \ \ FOR_LL( k , 0 , P ){ \ ll (&m_k)[NM] = m[k]; \ ll& m_size_k = m_size[k]; \ ll (&near_k)[P][2] = near[k]; \ ll (&E_min_k)[P] = E_min[k]; \ FOR_LL( h , 0 , k ){ \ ll (&m_h)[NM] = m[h]; \ ll& m_size_h = m_size[h]; \ ll (&near_kh)[2] = near_k[h]; \ ll& E_min_kh = E_min_k[h]; \ E_min_kh = 50000025; \ FOR_LL( i , 0 , m_size_k ){ \ ll& m_ki = m_k[i]; \ ll (&Ei)[NM] = E[m_ki]; \ FOR_LL( j , 0 , m_size_h ){ \ ll& m_hj = m_h[j]; \ ll& Eij = Ei[m_hj]; \ if( Eij < E_min_kh ){ \ ll& E_min_hk = E_min[h][k]; \ E_min_kh = E_min_hk = Eij; \ ll ( &near_hk )[2] = near[h][k]; \ near_kh[0] = near_hk[1] = m_ki; \ near_kh[1] = near_hk[0] = m_hj; \ } \ } \ } \ } \ ll (&near_kk)[2] = near_k[k]; \ if( m_size_k == 1 ){ \ near_kk[0] = near_kk[1] = m_k[0]; \ } else if( m_size_k > 1 ){ \ ll E_min_max_kk = -1; \ FOR_LL( i , 0 , m_size_k ){ \ ll& m_ki = m_k[i]; \ ll (&Ei)[NM] = E[m_ki]; \ ll E_min_kk = 50000025; \ ll m_ki_min; \ ll m_kj_min; \ FOR_LL( j , 0 , m_size_k ){ \ if( j != i ){ \ ll& m_kj = m_k[j]; \ ll& Eij = Ei[m_kj]; \ if( Eij < E_min_kk ){ \ E_min_kk = Eij; \ m_ki_min = m_ki; \ m_kj_min = m_kj; \ } \ } \ } \ if( E_min_kk > E_min_max_kk ){ \ E_min_max_kk = E_min_kk; \ near_kk[0] = m_ki_min; \ near_kk[1] = m_kj_min; \ } \ } \ } \ } \ \ template const ll& HeldKarp( const ll& k_start , const ll& k_goal , const ll& s , const ll (&k_valid)[P] , const ll& P_valid , const ll (&path_E)[NM][NM] , const ll (&near)[P][P][2] , const ll (&E_min)[P][P] , ll (&k_mid)[P] ); #define S 1 - 1 // #define S 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 - 1 int main() { // constexpr const ll N = 2; // constexpr const ll M = 1; // constexpr const ll Px = 1; // constexpr const ll Py = 1; // constexpr const ll N = 3; // constexpr const ll M = 4; // constexpr const ll Px = 1; // constexpr const ll Py = 1; constexpr const ll N = 100; constexpr const ll M = 8; constexpr const ll Px = 4; constexpr const ll Py = 4; constexpr const ll W = ( 1000 / Px ) + 1; constexpr const ll H = ( 1000 / Py ) + 1; constexpr const ll P = Px * Py; constexpr const ll NM = N + M; constexpr const ll path_lim = 100; constexpr const ll f_lim = 10000000000; CIN( ll , N_dummy ); CIN( ll , M_dummy ); ll a[NM]; ll b[NM]; ll p[NM]; ll m[P][NM]; ll m_size[P] = {}; FOR_LL( num , 0 , N ){ CIN( ll , a_num ); CIN( ll , b_num ); SetAB( a_num , b_num ); } ll E[NM][NM]; FOR_LL( i , 0 , N ){ ll (&Ei)[NM] = E[i]; FOR_LL( j , 0 , i ){ ll dx = a[i] - a[j]; ll dy = b[i] - b[j]; Ei[j] = E[j][i] = ( dx * dx + dy * dy ) * 25; } } ll E_min[P][P]; ll near[P][P][2]; SetNear; FOR_LL( num , N , NM ){ ll E_min_max = 0; ll k_max; ll h_max; FOR_LL( k , 0 , P ){ if( m_size[k] > 0 ){ ll (&E_min_k)[P] = E_min[k]; ll k_plus = k + 1; FOR_LL( h , 0 , k_plus ){ if( m_size[h] > 0 ){ ll& E_min_kh = E_min_k[h]; if( E_min_max < E_min_kh ){ E_min_max = E_min_kh; k_max = k; h_max = h; } } } } } ll E_min_max_min = 50000025; ll x_min; ll y_min; ll (&near_kh)[2] = near[k_max][h_max]; ll& i_min = near_kh[0]; ll& j_min = near_kh[1]; FOR_LL( x , 0 , 1001 ){ FOR_LL( y , 0 , 1001 ){ ll dix = a[i_min] - x; ll diy = b[i_min] - y; ll djx = a[j_min] - x; ll djy = b[j_min] - y; ll E_min_max_yx = ( dix * dix + diy * diy ) * ( i_min < N ? 5 : 1 ) + ( djx * djx + djy * djy ) * ( j_min < N ? 5 : 1 ); if( E_min_max_min > E_min_max_yx ){ E_min_max_min = E_min_max_yx; x_min = x; y_min = y; } } } cout << x_min << " " << y_min << endl; SetAB( x_min , y_min ); ll num_plus = num + 1; FOR_LL( i , N , num_plus ){ ll (&Ei)[NM] = E[i]; FOR_LL( j , 0 , i ){ ll dx = a[i] - a[j]; ll dy = b[i] - b[j]; Ei[j] = E[j][i] = ( dx * dx + dy * dy ) * ( j < N ? 5 : 1 ); } } SetNear; } ll P_valid = 0; ll k_valid[P]; FOR_LL( k , 0 , P ){ if( m_size[k] > 0 ){ k_valid[P_valid] = k; } P_valid++; } ll path[NM][NM][path_lim]; ll path_length[NM][NM]; ll path_E[NM][NM]; bool computed_path_E[NM][NM] = {}; FOR_LL( k , 0 , P_valid ){ ll (&m_k)[NM] = m[k_valid[k]]; ll& m_size_k = m_size[k_valid[k]]; // 手抜き ll length_lim = max( m_size_k + 3 , (ll)10 ); if( m_size_k == 1 ){ ll& m_ki = m_k[0]; path[m_ki][m_ki][0] = m_ki; path_length[m_ki][m_ki] = 1; path_E[m_ki][m_ki] = 0; computed_path_E[0][0] = true; } else if( m_size_k > 1 ){ FOR_LL( length , m_size_k , length_lim ){ ll f_min = 1; FOR_LL( i , 0 , length ){ f_min *= m_size_k; } f_min--; if( f_min >= f_lim ){ length = length_lim; } FOR_LL( f , f_min , f_lim ){ ll f_copy = f; ll path_current[path_lim]; bool used[NM] = {}; ll length_current = 0; ll i_start = f_copy % m_size_k; path_current[length_current] = i_start; used[i_start] = true; f_copy /= m_size_k; length_current++; while( length_current < length ){ ll i = f_copy % m_size_k; if( i != path_current[length_current - 1] ){ path_current[length_current] = i; used[i] = true; f_copy /= m_size_k; length_current++; } else { f_copy = 0; length_current = length; } } if( f_copy > m_size_k ){ f = f_lim; } else if( f_copy != 0 ){ bool used_all = true; FOR_LL( i , 0 , m_size_k ){ if( ! used[i] ){ used_all = false; i = m_size_k; } } if( used_all ){ ll path_E_current = 0; FOR_LL( i , 1 , length ){ ll& m_ki = m_k[path_current[i]]; ll& m_kj = m_k[path_current[i - 1]]; path_E_current += E[m_ki][m_kj]; } ll& i_finish = path_current[length - 1]; bool& computed_path_E_ij = computed_path_E[i_start][i_finish]; ll& path_E_ij = path_E[i_start][i_finish]; if( computed_path_E_ij ? path_E_ij > path_E_current : true ){ path_E_ij = path_E[i_finish][i_start] = path_E_current; ll (&path_ij)[path_lim] = path[i_start][i_finish]; ll (&path_ji)[path_lim] = path[i_finish][i_start]; FOR_LL( i , 0 , length ){ path_ij[i] = path_current[i]; path_ji[i] = path_current[length - 1 - i]; } path_length[i_start][i_finish] = path_length[i_finish][i_start] = length; if( ! computed_path_E_ij ){ computed_path_E_ij = computed_path_E[i_finish][i_start] = true; } } } } } } } } ll E_sum_min = 50000025 * P; ll k_start = p[0]; ll k_min = k_start; ll k_mid_min[P]; FOR_LL( k_next , 0 , P_valid ){ ll& k = k_valid[k_next]; if( k != k_start ){ ll s = S; s ^= ( 1 << k_start ); s ^= ( 1 << k ); ll k_mid[P]; ll E_sum = HeldKarp( k_start , k , 0 , k_valid , P_valid , path_E , near , E_min , k_mid ); E_sum += HeldKarp( k , k_start , s , k_valid , P_valid , path_E , near , E_min , k_mid ); E_sum += path_E[near[k_start][k][0]][near[k_mid[P_valid - 2]][k_start][1]] + path_E[near[k_start][k][1]][near[k][k_mid[1]][0]]; if( E_sum_min > E_sum ){ E_sum_min = E_sum; k_min = k; FOR_LL( k , 0 , P_valid ){ k_mid_min[k] = k_mid[k]; } } } } ll P_valid_minus = P_valid - 1; ll& near_k_start_0 = P_valid == 1 ? P_valid_minus : near[k_mid_min[P_valid - 2]][k_start][1]; ll& near_k_start_1 = P_valid == 1 ? P_valid_minus : near[k_start][k_min][0]; ll (&path_k_start)[path_lim] = path[near_k_start_0][near_k_start_1]; ll& path_length_k_start = path_length[near_k_start_0][near_k_start_1]; ll num_start; FOR_LL( num , 0 , path_length_k_start ){ if( path_k_start[num] == 0 ){ num_start = num; num = path_length_k_start; } } ll V = path_length_k_start; FOR_LL( k , 0 , P_valid_minus ){ ll& k_mid_min_k = k_mid_min[k]; ll& near_k_0 = near[k_mid_min[( k + P_valid_minus ) % P_valid ]][k_mid_min_k][1]; ll& near_k_1 = near[k_mid_min_k][k_mid_min[k+1]][0]; V += path_length[near_k_0][near_k_1]; } cout << V << endl; FOR_LL( num , num_start , path_length_k_start ){ ll& i = path_k_start[num]; if( i < N ){ cout << 1 << " " << i << endl; } else { cout << 2 << " " << i - N << endl; } } FOR_LL( k , 0 , P_valid_minus ){ ll& k_mid_min_k = k_mid_min[k]; ll& near_k_0 = near[k_mid_min[( k + P_valid_minus ) % P_valid ]][k_mid_min_k][1]; ll& near_k_1 = near[k_mid_min_k][k_mid_min[k+1]][0]; ll (&path_k)[path_lim] = path[near_k_0][near_k_1]; ll& path_length_k = path_length[near_k_0][near_k_1]; FOR_LL( num , 0 , path_length_k ){ ll& i = path_k[num]; if( i < N ){ cout << 1 << " " << i << endl; } else { cout << 2 << " " << i - N << endl; } } } FOR_LL( num , 0 , num_start ){ ll& i = path_k_start[num]; if( i < N ){ cout << 1 << " " << i << endl; } else { cout << 2 << " " << i - N << endl; } } return 0; } template const ll& HeldKarp( const ll& k_start , const ll& k_goal , const ll& s , const ll (&k_valid)[P] , const ll& P_valid , const ll (&path_E)[NM][NM] , const ll (&near)[P][P][2] , const ll (&E_min)[P][P] , ll (&k_mid)[P] ) { static ll answer_E[P][P][S]; static ll answer_mid[P][P][P]; static bool solved[P][P][S]; ll (&answer_mid_kskg)[P] = answer_mid[k_start][k_goal]; if( solved[k_start][k_goal][s] ){ ll P_valid_minus = P_valid - 1; FOR_LL( k , 0 , P_valid_minus ){ k_mid[k] = answer_mid_kskg[k]; } return answer_E[k_start][k_goal][s]; } if( s == 0 ){ k_mid[0] = answer_mid_kskg[0] = k_start; k_mid[1] = answer_mid_kskg[1] = k_goal; solved[k_start][k_goal][s] = true; return answer_E[k_start][k_goal][s] = answer_E[k_goal][k_start][s] = E_min[k_start][k_goal]; } ll s_copy = s; ll card = 0; ll k_s[P]; ll k_s_i = 0; while( s_copy != 0 ){ if( s_copy % 2 == 1 ){ k_s[card] = k_s_i; card++; } k_s_i++; } ll E_current_min = 7500003751; ll k_mid_current_min[P]; ll k_mid_current[P]; ll card_plus = card + 1; FOR_LL( i , 0 , card ){ ll& k = k_s[i]; ll E_current = HeldKarp( k_start , k , 0 , k_valid , P_valid , path_E , near , E_min , k_mid ); E_current += HeldKarp( k_start , k , s ^ ( 1 << k ) , k_valid , P_valid , path_E , near , E_min , k_mid_current ); E_current += path_E[near[k_start][k][1]][near[k][k_mid_current[1]][0]]; if( E_current_min < E_current ){ E_current_min = E_current; FOR_LL( j , 0 , card_plus ){ k_mid_current_min[j] = k_mid_current[j]; } } } answer_mid_kskg[0] = k_start; FOR_LL( i , 0 , card_plus ){ answer_mid_kskg[i+1] = k_mid[i+1] = k_mid_current_min[i]; } solved[k_start][k_goal][s] = true; return answer_E[k_start][k_goal][s] = answer_E[k_goal][k_start][s] = E_current_min; }