Codeforces #203, Division 2, C : Bombs

問題文

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

概要

平面上に N 個の爆弾があり、これらの爆弾ををロボットを使って処理する。
ロボットは特殊なコンテナを備えていて、一つの爆弾を持ち運ぶことができる。
ロボットにできる行動は以下の三種類である。

• 上下左右の四方向に任意の正整数距離進む（終点以外で爆弾を踏んではいけない）
• ロボットが踏んでいる爆弾をコンテナに入れる
• コンテナに入れた爆弾を解体し、コンテナは空になる（ 原点 ( 0, 0 ) でしか実行できない）

ロボットは最初原点 ( 0, 0 ) にいる。
必要な行動の数を最小化した上で全ての爆弾を処理できる処理手順を一つ出力せよ。

解法

爆弾のところまで行って回収し、原点まで戻ってきて解体する、というのが基本の戦略になります。
このとき、原点とのマンハッタン距離が近い順に処理することで、道中で爆弾を踏むことは無くなります。

コード

typedef pair<int,int> PII;
typedef vector<PII> VPII;

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

#define fst first
#define snd second

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

	int n;
	cin >> n;

	VPII bombs( n );
	FOR( b, bombs )
	{
		cin >> b.fst >> b.snd;
	}
	sort( ALL( bombs ), []( const PII &a, const PII &b ){ return abs( a.fst ) + abs( a.snd ) < abs( b.fst ) + abs( b.snd ); } );

	int k = 0;
	FOR( b, bombs )
	{
		k += 1;
		k += !( b.fst == 0 );
		k += !( b.snd == 0 );
	}
	k *= 2;

	cout << k << endl;
	FOR( b, bombs )
	{
		if ( 0 < b.fst )
		{
			cout << "1 " << b.fst << " R" << endl;
		}
		else if ( b.fst < 0 )
		{
			cout << "1 " << -b.fst << " L" << endl;
		}
		if ( 0 < b.snd )
		{
			cout << "1 " << b.snd << " U" << endl;
		}
		else if ( b.snd < 0 )
		{
			cout << "1 " << -b.snd << " D" << endl;
		}
		cout << 2 << endl;
		if ( 0 < b.fst )
		{
			cout << "1 " << b.fst << " L" << endl;
		}
		else if ( b.fst < 0 )
		{
			cout << "1 " << -b.fst << " R" << endl;
		}
		if ( 0 < b.snd )
		{
			cout << "1 " << b.snd << " D" << endl;
		}
		else if ( b.snd < 0 )
		{
			cout << "1 " << -b.snd << " U" << endl;
		}
		cout << 3 << endl;
	}

	return 0;
}