Codeforces 274C (168C) The Last Hole!

問題

座標平面上にn個の円がある。
それぞれの中心は(x[i], y[i])で、半径は時間tのときtである。

2個以上の円子によって囲まれた閉領域(円と円の隙間の領域のうち、閉じているもの)のうち、最も大きい時間Tに消滅するものの、消滅する時間Tを求めよ。

制約条件

n≦100

方針

editorial見た。
閉領域が1点につぶれるときの、つぶれる候補の点を列挙する。
候補の点が実際にその時間まで他の円により塗りつぶされなければOK.


候補となる点は、3つの円の中心が鋭角三角形をなすとき、その外心。
もしくは4つの円の中心が正方形をなすとき、その中心。
以上の列挙にO(n^3)かかり、さらにチェックにO(n)かかるため、全体でO(n^4)時間がかかる。

ソースコード

int main(){
	int n;
	cin >> n;
	G ps(n);
	rep(i, n) cin >> ps[i].real() >> ps[i].imag();
	set<P> S(all(ps));
	
	double ans = -1;
	rep(i, ps.size()) rep(j, i) rep(k, j){
		G g;
		g.pb(ps[i]); g.pb(ps[j]); g.pb(ps[k]);
		int a = -inf;
		double d;
		P p;
		//全ての角が鋭角であるか、dot積を見てチェック
		rep(m, 3){
			double t = dot(g[(m + 1) % 3] - g[m], g[(m + 2) % 3] - g[m]);
			int c = abs(t) < EPS ? 0 : t < 0 ? -1 : 1;
			if(a != -inf && a != c) goto FAIL;
			a = c;
		}
		p = circumcenter(g);
		d = abs(p - g[0]);
		rep(m, ps.size()) if(abs(ps[m] - p) < d - EPS) goto FAIL;
		ans = max(ans, d);
		FAIL:;
		//直角があるかdot積を見てチェック
		int r = -1;
		rep(m, 3) if(abs(dot(g[(m + 1) % 3] - g[m], g[(m + 2) % 3] - g[m])) < EPS){
			r = m;
			break;
		}
		if(r < 0) continue;
		//直角があったら、正方形になってるかを更にチェック
		p = g[(r + 1) % 3] + g[(r + 2) % 3] - g[r];
		if(!S.count(p)) continue;
		p = (p + g[r]) * 0.5;
		d = abs(p - g[r]);
		rep(m, ps.size()) if(abs(ps[m] - p) < d - EPS) goto FAIL2;
		ans = max(ans, d);
		FAIL2:;
	}
	printf("%.9f\n", ans);
	
	return 0;
}