fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sc( x ) scanf( "%d" , &x )
  5. #define REP( i , n ) for( int i = 0 ; i < n ; ++i )
  6. #define clr( t , val ) memset( t , val , sizeof( t ) )
  7.  
  8. #define pb push_back
  9. #define all( v ) v.begin() , v.end()
  10. #define SZ( v ) ((int)(v).size())
  11.  
  12. typedef long long ll;
  13. typedef vector< int > vi;
  14. typedef vector< ll > vll;
  15.  
  16. struct Point{
  17. 	int x , y , z;
  18. 	Point(){ x = y = z = 0;}
  19. 	Point( int x , int y , int z ) : x( x ) , y( y ) , z( z ){}
  20. };
  21. Point cross( const Point &A , const Point &B ){ return Point( A.y * B.z - B.y * A.z , -(A.x * B.z - A.z * B.x) , A.x * B.y - A.y * B.x );}
  22. bool operator == ( const Point &A , const Point &B ){ return A.x == B.x && A.y == B.y && A.z == B.z;}
  23. Point operator -( const Point &A , const Point &B ){ return Point( A.x - B.x , A.y - B.y , A.z - B.z );}
  24.  
  25. vll v;
  26. map< pair< ll , int > , int > memo;
  27. int n;
  28. int dp( ll mask , int pos ){
  29. 	if( mask == (1LL<<n) - 1 ) return 0;
  30. 	if( pos == SZ( v ) ) return n + 1;
  31. 	pair< ll , int > state( mask , pos );
  32. 	if( memo.count( state ) ) return memo[ state ];
  33. 	int &dev = memo[ state ] = dp( mask , pos + 1 );
  34. 	dev = min( dev , 1 + dp( mask | v[ pos ] , pos + 1 ) );
  35. 	return dev;
  36. }
  37. int main(){
  38. 	int x , y , z , tc = 0;
  39. 	while( sc( n ) == 1 ){
  40. 		if( n == 0 ) break;
  41. 		vector< Point > P;
  42. 		REP( i , n ){
  43. 			sc( x ) , sc( y ) , sc( z );
  44. 			P.pb( Point( x , y , z ) );
  45. 		}
  46. 		v.clear();
  47. 		//REP( i , n ) v.pb( 1LL << i );
  48. 		REP( i , n ){
  49. 			for( int j = i + 1 ; j < n ; ++j ){
  50. 				int mask = 0;
  51. 				mask |= (1LL << i);
  52. 				mask |= (1LL << j);
  53. 				REP( k , n )
  54. 					if( k != i && k != j && cross( P[ j ] - P[ i ] , P[ k ] - P[ i ] ) == Point() ) mask |= (1LL << k);
  55. 				v.pb( mask );
  56. 			}
  57. 		}
  58. 		memo.clear();
  59. 		if( n <= 3 )
  60. 		printf( "Target set %d can be cleared using only 1 shots.\n" , ++tc );
  61. 		else printf( "Target set %d can be cleared using only %d shots.\n" , ++tc , dp( 0 , 0 ) );
  62. 		//cout << SZ( memo ) << endl;
  63. 	}
  64. }
  65.  
Success #stdin #stdout 0s 3344KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/0nT7nU
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!