AOJ 2181 Neko's Treasure

問題

平面上に猫とねずみがいて、それぞれの座標が与えられる。
猫とねずみの間に、円周の形をした壁をいくつか置くことができる。
それぞれの候補は中心(x, y)および半径rにより与えられる。

壁は、候補の中からいくつでも選んで置くことができるが、
交わったり触ったりする壁を選ぶとはできない。

壁を適切に選ぶとき、ねずみは猫のところまで行くのにいくつの壁を越えなければならないか、求めよ。

制約条件

壁の数≦1000

方針

猫とねずみ、一方のみを囲む壁のみを考えればよい。
（両方を囲む、あるいは両方を囲まない壁は置いても意味がない）

壁の包含関係をグラフにする。
猫を囲む壁のうち、一番外側のもの、ねずみを囲む壁のうち一番外側のものを決めると、
残りの壁の個数は、それぞれのグラフにおけるDAGの最長鎖の長さになる。
DAGの最長鎖の長さはメモ化再帰すれば簡単に求まる。

ソースコード

int n, r[1000];
int dp[1000];
P p[1000];

int rec(int c, const vi &idx){
	int &res = dp[c];
	if(res >= 0) return res;
	res = 0;
	rep(i, idx.size()) if(abs(p[c] - p[idx[i]]) + EPS < r[c] - r[idx[i]])
		res = max(res, rec(idx[i], idx));
	
	return ++res;
}

int main(){
	while(cin >> n, n){
		vi a, b;
		P pa, pb;
		int ans = 0;
		cin >> pa.real() >> pa.imag() >> pb.real() >> pb.imag();
		rep(i, n){
			cin >> p[i].real() >> p[i].imag() >> r[i];
			bool fa = abs(p[i] - pa) < r[i];
			bool fb = abs(p[i] - pb) < r[i];
			if(fa != fb){
				if(fa) a.pb(i);
				else b.pb(i);
			}
		}
		
		memset(dp, -1, sizeof(dp));
		rep(i, a.size()) rep(j, b.size()){
			if(abs(p[a[i]] - p[b[j]]) < r[a[i]] + r[b[j]] + EPS) continue;
			ans = max(ans, rec(a[i], a) + rec(b[j], b));
		}
		rep(i, a.size()) ans = max(ans, rec(a[i], a));
		rep(i, b.size()) ans = max(ans, rec(b[i], b));
		cout << ans << endl;
	}
	return 0;
}