torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #165, Division 2, A : Fancy Fence

概要

整数が t 個与えられる。
それぞれについて、与えられた角度 a を内角とする正多角形が存在するかどうか求めよ。

解法

正 n 角系の一つの内角は、\frac{180(n-2)}{n} で求められます。
例えば、適当に n = 1000 とすると 179 を超えるので a の制約に対して十分であることが分かります。
なので、n を 3 から 1000 まで動かして正多角形の角度を(整数であるもののみ)求めておきます。
あとは、各 a に対して先程求めたリストの中に含まれるかどうかを見ればよいです。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

VI getAngles()
{
	VI res;

	REP( n, 3, 1001 )
	{
		int tmp = 180 * ( n - 2 );

		if ( !( tmp % n ) )
		{
			res.PB( tmp / n );
		}
	}

	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	EACH( a, as )
	{
		cin >> a;
	}

	VI angles( getAngles() );

	EACH( a, as )
	{
		cout << ( binary_search( ALL( angles ), a ) ? "YES" : "NO" ) << endl;
	}

	return 0;
}