『ACM/ICPC国内予選突破の手引き』をやってみる（６）

AIZU Online Judge C/C++

ACM/ICPC国内予選突破の手引き”Step by step”の難易度：☆☆☆ ４つ目から終わりまで。
下から2番目の”Non-Stop Travel”はAOJで見つからなかった上に問題文が英語なので、見なかったことにした。
ともあれ、これで”Step by step”は終わり。がんばった！
あとはJOI本選の過去問やろうかなぁ…。


Problem 1132 : Circle and Points

  • 難易度 : ☆☆☆
  • 種類 : 幾何

珍しく解法を思いついた！
と思ったら、"ある2点を通る円"の求め方を忘れるという体たらく。
解き方は解説にあるのと同じで、ある2点を円周上に持つ円を求めて、その内側にある点をカウントしていく。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;


typedef struct POINT_TAG {
	double x;
	double y;
} POINT;

int n;
vector<POINT> dots;

// 2点間の距離を返す
double distance( double x1, double y1, double x2, double y2 )
{
	return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
}

// 引数は円の中心の座標。円の内側にある点の数をカウントして返す。
int count( double x, double y )
{
	int cnt = 0;

	for( int i=0; i<n; i++ )
		if( distance( dots[i].x, dots[i].y, x, y ) < 1.0 + 1e-10 )
			cnt++;

	return cnt;
}

int main(void)
{
	POINT work;
	int max, new_val;
	int a[2] = { 1, -1 };
	int i, j, k;
	double d, mx, my, vx, vy, m;


	while( cin >> n, n != 0 ){
		dots.clear();
		// 入力
		for( i=0; i<n; i++ ){
			cin >> work.x >> work.y;
			dots.push_back(work);
		}

		max = 1;
		for( i=0; i<n; i++ ){
			for( j=i; j<n; j++ ){
				// 2点間の距離
				d = distance( dots[i].x, dots[i].y, dots[j].x, dots[j].y );
				if( d > 2.0 + 1e-10 )
					continue;

				// 2点を結ぶ線分の中点の座標
				mx = ( dots[i].x + dots[j].x ) / 2;
				my = ( dots[i].y + dots[j].y ) / 2;
				// 2点を結ぶ線分の単位ベクトル
				vx = ( dots[i].x - dots[j].x ) / d;
				vy = ( dots[i].y - dots[j].y ) / d;
				// いくつ動かすか
				m = sqrt( 1.0 - d*d/4.0 );

				// 点のカウント
				for( k=0; k<2; k++ ){
					new_val = count( mx+a[k]*m*vy, my-a[k]*m*vx );
					if( max < new_val ){
						max = new_val;
					}
				}
			}
		}

		//	結果の出力
		cout << max << endl;

	}

	return 0;
}

Problem 2009 : Area Separation

  • 難易度 : ☆☆☆
  • 種類 : 幾何

交点を数えればいいということには気づいたんだけど、その交点の座標の求め方がわからず…。
解説見てcomplex初挑戦。
最近の練習はもはや写経な気がする。

#include <iostream>
#include <vector>
#include <complex>

using namespace std;

typedef complex<double> P;
#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) (EQ((a).real(),(b).real())&&EQ((a).imag(),(b).imag()))


double cross( P a, P b )
{
	return ( a.real()*b.imag() - a.imag()*b.real() );
}

int main(void)
{
	int n, cnt;
	int i, j, k;
	vector<P> points;
	vector<P> s, e;

	while( cin >> n, n != 0 ){
		s.resize(n); e.resize(n);

		// 入力
		int x[2], y[2];
		for( i=0; i<n; i++ ){
			cin >> s[i].real() >> s[i].imag();
			cin >> e[i].real() >> e[i].imag();
		}

		cnt = 1;
		for( i=0; i<n; i++ ){
			points.clear();
			cnt++;

			for( j=0; j<i; j++ ){
				P iv = e[i]-s[i];
				P jv = e[j]-s[j];

				if( abs( cross( iv, jv ) ) < EPS )
					continue;

				P point = s[i] + iv*cross( jv, s[j]-s[i] ) / cross( jv, iv );
				if( abs( point.real() ) > 100.0-EPS ) continue;
				if( abs( point.imag() ) > 100.0-EPS ) continue;

				for( k=0; k<points.size(); k++ )
					if( EQV( point, points[k] ) )
						break;
				if( k == points.size() ){
					cnt++;
					points.push_back(point);
				}
			}

		}

		// 結果の出力
		cout << cnt << endl;

	}

	return 0;
}

Problem 1140 : Cleaning Robot

  • 難易度 : ☆☆☆
  • 種類 : グラフ

種類にグラフと書いてあったおかげで解けた。
幅探索って慣れない。時間かけすぎた。

#include <iostream>
#include <string>
#include <deque>

using namespace std;

#define MAX 20


int w, h;				// マップの大きさ
int map[MAX+2][MAX+2];	// マップ（0:通行不可, 1:通行可）
int n_dt;				// 汚れた床の数
int x_dt[12], y_dt[12];	// 汚れた床の座標（＋最後にロボットの初期位置）
int dist[12][12];		// 汚れた床・ロボット同士の距離行列
int ans;				// 最小値

// 距離を求めて距離行列へ代入する
bool getDistance( int num, int x0, int y0 )
{
	// 通過済みか
	bool v[MAX+2][MAX+2];
	// 距離を保存
	int d[MAX+2][MAX+2];

	// 探索用
	int vx[4] = { 0, 1, 0, -1 };
	int vy[4] = { 1, 0, -1, 0 };
	int cx, cy, new_x, new_y;
	int i, j;
	deque<int> x; deque<int> y;

	for( i=0; i<=MAX+1; i++ ){
		for( j=i; j<=MAX+1; j++ ){
				d[i][j] = d[j][i] = -1;
				v[i][j] = v[j][i] = false;
		}
	}

	d[y0][x0] = 0;
	x.push_back(x0); y.push_back(y0);

	//　幅優先探索で元の床からの距離を求める
	while( x.size() > 0 ){
		// 値の取り出し
		cx = x[0]; cy = y[0];
		x.pop_front(); y.pop_front();
		if( v[cy][cx] ) continue;
		v[cy][cx] = true;

		for( i=0; i<4; i++ ){
			new_x = cx + vx[i];
			new_y = cy + vy[i];

			if( !map[new_y][new_x] ) continue;	// 通行不可
			if( v[new_y][new_x] ) continue;		// 通過済み

			d[new_y][new_x] = d[cy][cx] + 1;
			x.push_back(new_x); y.push_back(new_y);
		}
	}

	// 距離行列への代入
	for( i=0; i<=n_dt; i++ ){
		dist[num][i] = dist[i][num] = d[y_dt[i]][x_dt[i]];
		// 到達不可であればfalseを返す
		if( dist[num][i] == -1 )
			return false;
	}

	return true;
}

// 深さ優先探索で最短の値を探す
void checkRoute( int cnt, bool v[], int num )
{
	int i;

	// 暫定のの最小値より現在の値が大きいとき
	if( ans < cnt )
		return;

	// 全て通過した
	for( i=0; i<n_dt; i++ )
		if( !v[i] )
			break;
	if( i == n_dt ){
		if( ans > cnt )
			ans = cnt;
		return;
	}

	// 次の床へ
	for( i=0; i<n_dt; i++ ){
		if( !v[i] ){
			v[i] = true;
			checkRoute( cnt+dist[num][i], v, i );
			v[i] = false;
		}
	}

	return;
}

int main(void)
{
	int rx, ry, i, j;
	string input;

	while( cin >> w >> h, w != 0 && h != 0 ){
		// 初期化
		for( i=0; i<=MAX+2; i++ )
			for( j=0; j<=MAX+2; j++ )
				map[i][j] = 0;

		// 入力
		n_dt = 0;
		for( i=1; i<=h; i++ ){
			cin >> input;
			for( j=0; j<input.size(); j++ ){
				if( input[j] != 'x' )
					map[i][j+1] = 1;

				if( input[j] == '*' ){
					x_dt[n_dt] = j+1;
					y_dt[n_dt] = i;
					n_dt++;
				}
				if( input[j] == 'o' ){
					rx = j+1;
					ry = i;
				}
			}
		}

		// ロボットの座標を汚れた床の座標を格納している配列の最後に追加する
		x_dt[n_dt] = rx;
		y_dt[n_dt] = ry;

		// 汚れた床（＋ロボット）同士の距離行列を求める
		for( i=0; i<n_dt; i++ ){
			if( !getDistance( i, x_dt[i], y_dt[i] ) ){	// 到達不可な汚れた床がある
				cout << -1 << endl;
				break;
			}
		}
		if( i != n_dt )
			continue;

		bool v[12];
		for( i=0; i<=10; i++ )
			v[i] = false;

		ans = 401;
		// 深さ優先で最短の値を求める
		for( i=0; i<n_dt; i++ ){
			v[i] = true;
			checkRoute( dist[n_dt][i], v, i );
			v[i] = false;
		}

		// 結果の表示
		if( ans == 401 )
			cout << -1 << endl;
		else
			cout << ans << endl;

	}

	return 0;
}