立命館合宿2013 1日目 F Balloon Contest

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/contest_status.jsp?id=RitsCamp13Day1）

制約条件

n≦100
m≦10

方針

全員の移動速度は同じなので、
Aの人がボールを取れる⇔Aの人が一番近い領域にボールが落ちる、
ということが言える。

これはAのボロノイ領域。

Aのボロノイ領域にボールが落ちる確率は、
(Aのボロノイ領域とボールが落ちる長方形の交わりの面積) / (ボールの落ちる全体の面積)
であるので、図形の交わりの面積を求めれば確率が簡単にもとまる。

ボロノイ領域は愚直にやり、図形の交わりも愚直に切った。
制約が小さいので余裕で通る。

ソースコード

G voronoi(const G &g, G S, int idx){
	rep(i, g.size()) if(i != idx){
		P d = (g[i] - g[idx]) * P(0, 1);
		P m = (g[i] + g[idx]) * 0.5;
		L l(m, m + d);
		S = convex_cut(S, l);
	}
	return S;
}
G convex_is(G g, const G &e){
	rep(i, e.size()) g = convex_cut(g, L(e[i], e[(i + 1) % e.size()]));
	return g;
}
double area(const G &g){
	double a = 0;
	rep(i, g.size()) a += cross(curr(g, i), next(g, i));
	return abs(a) / 2;
}

int n, m;

int main(){
	while(cin >> n >> m, n){
		G g(n);
		rep(i, n) cin >> g[i].real() >> g[i].imag();
		vector<G> voro;
		
		G S;
		S.pb(P(-inf, -inf));
		S.pb(P(inf, -inf));
		S.pb(P(inf, inf));
		S.pb(P(-inf, inf));
		
		double e[100] = {};
		rep(i, n) voro.pb(voronoi(g, S, i));
		
		rep(i, m){
			G rect;
			P p;
			double dy, dx, s;
			cin >> p.real() >> p.imag() >> dx >> dy >> s;
			
			rect.pb(P(-dx, -dy));
			rect.pb(P(dx, -dy));
			rect.pb(P(dx, dy));
			rect.pb(P(-dx, dy));
			rep(j, 4) rect[j] += p;
			
			rep(j, n){
				G a = convex_is(rect, voro[j]);
				e[j] += s * area(a) / dx / dy / 4;
			}
		}
		printf("%.9f\n", *max_element(e, e + n));
	}
	return 0;
}