概要
二次元平面上の 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; }