Codeforces 394(#231 Div1) E. Lightbulb for Minister

問題

n個の点および凸なm角形が与えられる。
m角形の内部で、n個の点からの距離の二乗の和が最小になる場所における、
距離の二乗の和の最小値を求めよ。

制約条件

n≦10^5
m≦10^5
座標の絶対値は10^6以下

方針

n個の点からの距離の二乗の和をf(x, y)とする。これを最小化したい。

m角形の内部という条件がなかったら、単に二変数の二次関数の最小値なので、
grad f = 0となる点が答え。
すなわち、Σx[i] - nx = 0, Σy[i] - ny = 0なので、単に重心。

重心が多角形の内部に入っていなかったときが問題で、
f(x, y)の等高線を考えてみると、これはx^2の係数とy^2の係数が等しいので円になっている。
なので、f(x, y)を最小にするような点はm角形の辺上か頂点のどれかであるはずで、
辺上にあるときは、その辺の両端のうちどちらかは、頂点の中でf(x, y)を最小にする頂点。

なので、f(x, y)が最小になる頂点の周りだけで最小値を探してやればよい。
二次関数なので直接最小値が求まるけれど、３分探索とかをしてもギリギリ間に合う。

ソースコード

int n, m;
double ax, bx, cx, ay, by, cy;

double dist(P p){
	double res = 0;
	res += ax * p.real() * p.real() - bx * p.real() + cx;
	res += ay * p.imag() * p.imag() - by * p.imag() + cy;
	return res;
}
double solve(P p, P q){
	double l = 0, r = 1;
	rep(it, 100){
		double a = (l * 2 + r) / 3, b = (l + r * 2) / 3;
		if(dist(p * a + q * (1 - a)) < dist(p * b + q * (1 - b))) r = b;
		else l = a;
	}
	return dist(p * l + q * (1 - l));
}

int main(){
	cin >> n;
	G p(n);
	P g;
	ax = ay = n;
	rep(i, n){
		cin >> p[i].real() >> p[i].imag();
		g += p[i] / (double)n;
		bx += p[i].real() * 2;
		by += p[i].imag() * 2;
		cx += p[i].real() * p[i].real();
		cy += p[i].imag() * p[i].imag();
	}
	cin >> m;
	G q(m);
	rep(i, m) cin >> q[i].real() >> q[i].imag();
	
	if(contains(q, g) != OUT){
		printf("%.9f\n", dist(g));
		return 0;
	}
	
	double mn = 1e20;
	int mni;
	
	rep(i, m){
		double d2 = dist(q[i]);
		if(d2 < mn){
			mn = d2;
			mni = i;
		}
	}
	
	double ans = solve(q[(mni + m - 1) % m], q[mni]);
	ans = min(ans, solve(q[mni], q[(mni + 1) % m]));
	printf("%.9f\n", ans);
	
	return 0;
}