概要
N 本の釘を平板に打ち付け、全ての釘が内部に収まるように輪ゴムを引っ掛けて囲う。
このとき、輪ゴムに接していない釘の本数を出力せよ。
解法
輪ゴムに接する点は、与えられた点集合の凸包と等しくなります。
従って、点の数から、凸包に含まれる点の数を減ずると答えが得られます。
凸法を求める部分には Graham Scan を用いています。(蟻本参照)
コード
#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() struct Point { double x, y; Point() : x( 0 ), y( 0 ) { return; } Point( double x, double y ) : x( x ), y( y ) { return; } Point operator + ( const Point &a ) const { return Point( x + a.x, y + a.y ); } Point operator - ( const Point &a ) const { return Point( x - a.x, y - a.y ); } Point operator * ( const double &a ) const { return Point( x * a, y * a ); } Point operator / ( const double &a ) const { return Point( x / a, y / a ); } bool operator < ( const Point &a ) const { return x == a.x ? y < a.y : x < a.x; } }; // 外積 double cross( const Point &a, const Point &b ) { return a.x * b.y - a.y * b.x; } // Graham Scan vector< Point > getConvex( vector< Point > ps ) { const int N = ps.size(); sort( ALL( ps ) ); int k = 0; vector< Point > convex( N * 2 ); for ( int i = 0; i < N; i++ ) { while ( 2 <= k && cross( convex[ k - 1 ] - convex[ k - 2 ], ps[i] - convex[ k - 1 ] ) <= 0 ) { k--; } convex[ k++ ] = ps[i]; } for ( int i = N - 2, t = k; 0 <= i; i-- ) { while ( t < k && cross( convex[ k - 1 ] - convex[ k - 2 ], ps[i] - convex[ k - 1 ] ) <= 0 ) { k--; } convex[ k++ ] = ps[i]; } convex.resize( k - 1 ); return convex; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); while ( true ) { int n; cin >> n; if ( !n ) { break; } vector< Point > ps( n ); EACH( p, ps ) { char d; cin >> p.x >> d >> p.y; } vector< Point > convex = getConvex( ps ); cout << n - convex.size() << endl; } return 0; }