Atcoder Regular Contest #011 D - きつねさんからの挑戦状

幾何

問題

日本語なので本文参照（http://arc011.contest.atcoder.jp/tasks/arc011_4）


座標平面上で、n本の直線a[i]x + b[i]y + c[i] = 0および、
m個の点の座標と、ある整数Rが与えられる。


座標平面上の点(x, y)（|x|, |y|≦R）に対して、
最も近い直線との距離をa, 最も近い点との距離をbとする。
f(x, y) = a + b^2とするとき、
f(x, y)の最大値を求めよ。

制約条件

n, m≦16

方針

いるごさまの解説の通り。
http://topcoder.g.hatena.ne.jp/ir5/20130119


最大値を取るような点は、

  • 点と点の二等分線、
  • 正方形の辺
  • 角の二等分線

の交点のどれか。

交点はそんなに多くないので、全て列挙して、
それぞれでf(x, y)を求める。

ソースコード

int n, m, r;
int a[20], b[20], c[20];


int main()
{
	G ps;
	vector<L> ls;
	cin >> n >> m >> r;
	
	rep(i, n){
		cin >> a[i] >> b[i] >> c[i];
		if(a[i] == 0){
			ls.pb(L(P(0, -c[i] * 1.0 / b[i]), P(1, -c[i] * 1.0 / b[i])));
		}else if(b[i] == 0){
			ls.pb(L(P(-c[i] * 1.0 / a[i], 0), P(-c[i] * 1.0 / a[i], 1)));
		}
		else{
			ls.pb(L(P(0, -c[i] * 1.0 / b[i]), P(1, -(c[i] + a[i]) * 1.0 / b[i])));
		}
	}
	rep(i, m){
		int a, b;
		cin >> a >> b;
		ps.pb(P(a, b));
	}
	
	vector<L> l;
	G g;
	g.pb(P(-r, -r)); g.pb(P(r, -r));
	g.pb(P(r, r)); g.pb(P(-r, r));
	rep(i, 4) l.pb(L(g[i], g[(i + 1) % 4]));
	
	rep(i, n) rep(j, i){
		vector<L> v = bisectionLL(ls[i], ls[j]);
		rep(it, v.size()) l.pb(v[it]);
	}
	rep(i, m) rep(j, i) l.pb(bisectionPP(ps[i], ps[j]));
	
	double mx = -1;
	rep(i, l.size()) rep(j, i){
		if(!intersectLL(l[i], l[j])) continue;
		P p = crosspoint(l[i], l[j]);
		double mnp = INF, mnl = INF;
		
		if(p.real() < -r || p.real() > r) continue;
		if(p.imag() < -r || p.imag() > r) continue;
		
		rep(k, n) mnl = min(mnl, distanceLP(ls[k], p));
		rep(k, m) mnp = min(mnp, abs(p - ps[k]));
		mx = max(mx, mnl + mnp * mnp);
	}
	printf("%.9f\n", mx);
	
	return 0;
}