Codeforces 159, C : View Angle

問題文

http://codeforces.com/contest/257/problem/C

概要

二次元平面上の n 個の点の座標が与えられる。
全ての点を内部に含むような角度の内、最小のものを度数法で出力せよ。

解法

まず、全ての点についてその（ x 軸からの）角度を求めソートします。
（一番小さい角については、360°を足した上で末尾に追加しておきます）
すると、角度的に、隣合う点の間に他の点は存在しないので、他の点はそれ以外の部分に存在します。
従って、その角度を a として 360° - a の範囲に全ての点が収まります。
隣合う点の間の角度の最大値を求め、360°から減ずることで答えが得られます。

コード

typedef pair<int,int> PII;

#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 )

#define fst first
#define snd second

const double PI = acos( -1 );

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

	int n;
	cin >> n;

	if ( n == 1 )
	{
		cout << 0 << endl;
		return 0;
	}

	vector< PII > ps( n );
	EACH( p, ps )
	{
		cin >> p.fst >> p.snd;
	}

	vector<double> degs;
	transform( ALL( ps ), back_inserter( degs ),
			[]( pair<double,double> a ) -> double { return atan2( a.snd, a.fst ); } );
	sort( ALL( degs ) );
	degs.PB( degs[0] + 2 * PI );

	double res = 0;

	REP( i, 0, n )
	{
		res = max( res, abs( degs[ i + 1 ] - degs[i] ) );
	}

	res = 360 - res * 180 / PI;

	cout.precision( 7 );
	cout << fixed;
	cout << res << endl;
		
	return 0;
}