torus711 のアレ

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

AOJ 0068 : Enclose Pins with a Rubber Band

概要

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;
}