题意

给定一个由 $n$ 个点组成的凸包， $q$ 次询问，每次询问给出一个圆，求出从凸包到圆各处最小期望长度。

$n,q\leq5000$ 。

题解

如果圆心在凸包里直接从圆心出发，否则看圆心到凸包的距离。

代码

const int N = 5010;
const ld eps = 1e-6;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, q;
	int sgn(ld x) {
		if (x < -eps) return -1;
		if (x >  eps) return 1;
		return 0;
	}
	typedef complex<ld> vec;
	ld dot(vec a, vec b) { return real(a) * real(b) + imag(a) * imag(b); }
	ld cross(vec a, vec b) { return real(a) * imag(b) - imag(a) * real(b); }
	
	vec a[N];
	bool inhull(vec p) {
		for (int i = 0; i < n; ++i)
			if (sgn(cross(a[i] - p, a[(i + 1) % n] - p)) <= 0) return 0;
		return 1;
	}
	ld dis(vec p, vec a, vec b) {
		if (abs(b - a) > eps && sgn(dot(p - a, b - a)) >= 0 && sgn(dot(p - b, a - b)) >= 0)
			return fabs(cross(p - a, b - a)) / abs(b - a);
		return min(abs(p - a), abs(p - b));
	}
	int main () {
		n = read(), q = read();
		for (int i = 0; i < n; ++i) {
			int x = read(), y = read();
			a[i] = vec(x, y);
		}
		while (q--) {
			int x = read(), y = read(); vec A = vec(x, y);
			x = read(), y = read(); vec B = vec(x, y);
			vec O = (A + B) / (ld)2.0;
			ld r = abs(O - A), d = 1e18;
			if (inhull(O)) d = 0;
			else {
				for (int i = 0; i < n; ++i)
					d = min(d, dis(O, a[i], a[(i + 1) % n]));
			}
			printf ("%.9Lf\n", ((long double) r * r / 2 + (long double) d * d));
		}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}