CF575E Spectator Riots 题解

CF575E Spectator Riots

题意

• 给定整点集 $\mathcal S = \\{(x,y)|x,y \in [0,10^5]\\}$。
• 给定另外 $n$ 个整点集 $\mathcal P_{1\dots n}$，对于 $i \in [1,n]$，给定 $x_i,y_i,v_i$，$\mathcal P_i = \mathcal S \cap \\{(x,y)||x-x_i|+|y-y_i| \in [0,v_i]\\}$。
• 有 $n$ 个整点 $p_{1\dots n}$，对于 $i \in [1,n]$，$p_i$ 在 $\mathcal P_i$ 中等概率随机。
• 你需要从点集 $\bigcup_{i=1}^n \mathcal P_i$ 中选择三个不共线的点，使这三个点的外接圆期望所覆盖（包括圆周上）的 $p$ 点最多。如果有多种方案，则要求这个外接圆的半径最大。如果还有多种方案，任何一种都可以。
• 你求出的半径与答案的误差应 $\le 0.01$，答案的半径 $\le 10^{10}$。
• $n \le 10^5$，$(x_i,y_i) \in \mathcal S$ 且不全都共线，$v_i \le 10^3$。

题解

题意看着很厉害的样子，那么考虑优化题意！

题意实际上就是说，平面上有 $n$ 个区域，每个区域有一个点在其中等概率随机，要求找到一个最大的圆，能够期望覆盖住尽可能多的点。

那让这个圆覆盖住所有区域不就完了吗？还什么「期望」，还什么「尽可能多」，全覆盖住不就是最多的了吗？

那就直接来个无限大的圆？等等，有个小问题，题意要求这个圆要是三个区域内的点的外接圆。怎么办？

考虑把这个无限大的圆一直变小一直变小一直变小，直到它在能够覆盖所有区域的情况下，恰好经过至少三个所有区域的凸包上的点。

似乎已经做完了？等等，还有个小问题，题意还要求半径最大。又该怎么办呢？

想想半径最大的是什么？是直线啊！那这题不让直线怎么办？那就尽可能的直！什么情况下能尽可能的直？凸包上相邻的三个点！

然后就真的做完了。

代码

const int M = 1e5;

inline vector<P> convex_hull(vector<P> a) {
	sort(a.begin(), a.end());
	int n = unique(a.begin(), a.end()) - a.begin();
	vector<P> p;
	for (int i = 0; i < n; i++) {
		while (p.size() > 1u &&
			(p.back() - p[p.size()-2]) % (a[i] - p[p.size()-2]) < eps)
				p.pop_back();
		p.pb(a[i]);
	}
	ui m = p.size();
	for (int i = n - 2; ~i; i--) {
		while (p.size() > m &&
			(p.back() - p[p.size()-2]) % (a[i] - p[p.size()-2]) < eps)
				p.pop_back();
		p.pb(a[i]);
	}
	p.pop_back();
	return p;
}

inline ld calc(P x, P y, P z) {
	P a = y - x, b = z - x, c = z - y;
	return a.l() * b.l() * c.l() / (2 * (a % b));
}

int main() {
	int n;
	rd(n);
	vector<P> a;
	for (int i = 1, x, y, v; i <= n; i++) {
		rd(x), rd(y), rd(v);
		vector<P> p;
		p.pb(P(0, 0)), p.pb(P(0, M)), p.pb(P(M, 0)), p.pb(P(M, M));
		p.pb(P(x, y + v)), p.pb(P(x, y - v));
		p.pb(P(x + v, y)), p.pb(P(x - v, y));
		vector<L> l1, l2;
		l1.pb(L(p[0], p[1])), l1.pb(L(p[0], p[2]));
		l1.pb(L(p[3], p[1])), l1.pb(L(p[3], p[2]));
		l2.pb(L(p[4], P(1, 1))), l2.pb(L(p[4], P(1, -1)));
		l2.pb(L(p[5], P(1, 1))), l2.pb(L(p[5], P(1, -1)));
		for (L u : l1) for (L v : l2) p.pb(u * v);
		for (P o : p) {
			if (o.x < -eps || o.x > M + eps) continue;
			if (o.y < -eps || o.y > M + eps) continue;
			if (abs(o.x - x) + abs(o.y - y) < -eps) continue;
			if (abs(o.x - x) + abs(o.y - y) > v + eps) continue;
			a.pb(o);
		}
	}
	a = convex_hull(a);
	n = a.size();
	a.pb(a[0]), a.pb(a[1]);
	ld ans = 0;
	int p = -1;
	for (int i = 0; i < n; i++) {
		ld now = calc(a[i], a[i+1], a[i+2]);
		if (now > ans) ans = now, p = i;
	}
	print((int)(a[p].x + 0.5L), ' '), print((int)(a[p].y + 0.5L));
	print((int)(a[p+1].x + 0.5L), ' '), print((int)(a[p+1].y + 0.5L));
	print((int)(a[p+2].x + 0.5L), ' '), print((int)(a[p+2].y + 0.5L));
	return 0;
}