# CFR 8 C. Looking for Order ( Bitmask, DP )

Problem - 8C - Codeforces

The first line of the input file contains the handbag's coordinates xs, ys. The second line contains number n (1 ≤ n ≤ 24) — the amount of objects the girl has. The following n lines contain the objects' coordinates. All the coordinates do not exceed 100 in absolute value. All the given positions are different. All the numbers are integer.
TL: 4000 ms

O( N * 2^N ) / O( 2^N )

```#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
if( x <= v ) return 0;
x = v; return 1;
}

int sqr( int x ){
return x * x;
}

signed main(){
ios::sync_with_stdio( 0 );
int sx, sy; cin >> sx >> sy;
int n; cin >> n;
vector< int > x( n ), y( n );
for( int i = 0; i < n; ++i ){
cin >> x[ i ] >> y[ i ];
x[ i ] -= sx;
y[ i ] -= sy;
}
vector< int > dp( 1 << n, 0x3f3f3f3f );
vector< int > pre( 1 << n );
dp[ 0 ] = 0;
for( int s = 0; s < 1 << n; ++s ){
int i = __builtin_ctz( ~s );
if( upmin( dp[ s | 1 << i ], dp[ s ] + 2 * ( sqr( x[ i ] ) + sqr( y[ i ] ) ) ) ){
pre[ s | 1 << i ] = s;
}
for( int j = 0; j < n; ++j ){
if( i == j ) continue;
if( s >> j & 1 ) continue;
if( upmin( dp[ s | 1 << i | 1 << j ], dp[ s ] + sqr( x[ i ] ) + sqr( y[ i ] )
+ sqr( x[ i ] - x[ j ] ) + sqr( y[ i ] - y[ j ] )
+ sqr( x[ j ] ) + sqr( y[ j ] ) ) ){
pre[ s | 1 << i | 1 << j ] = s;
}
}
}
cout << dp[ ( 1 << n ) - 1 ] << endl;
vector< int > ans = { 0 };
for( int s = ( 1 << n ) - 1; s; s = pre[ s ] ){
int ps = pre[ s ];
vector< int > dc;
for( int i = 0; i < n; ++i ){
if( ( s >> i & 1 ) != ( ps >> i & 1 ) ){
dc.emplace_back( i );
}
}
if( dc.size() == 1 ){
ans.emplace_back( dc[ 0 ] + 1 );
ans.emplace_back( 0 );
} else{
ans.emplace_back( dc[ 0 ] + 1 );
ans.emplace_back( dc[ 1 ] + 1 );
ans.emplace_back( 0 );
}
}
for( int i = ans.size() - 1; i >= 0; --i ){
cout << ans[ i ] << " \n"[ i == 0 ];
}
return 0;
}
```