题解 CF575E 【Spectator Riots】

xht

2020-02-20 22:52:59

Solution

> [CF575E Spectator Riots](https://codeforces.com/contest/575/problem/E) ## 题意 - 给定整点集 $\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$ 个区域,每个区域有一个点在其中等概率随机,要求找到一个最大的圆,能够期望覆盖住尽可能多的点。 那让这个圆覆盖住所有区域不就完了吗?还什么「期望」,还什么「尽可能多」,全覆盖住不就是最多的了吗? 那就直接来个无限大的圆?等等,有个小问题,题意要求这个圆要是三个区域内的点的外接圆。怎么办? 考虑把这个无限大的圆一直变小一直变小一直变小,直到它在能够覆盖所有区域的情况下,恰好经过至少三个**所有区域的凸包**上的点。 似乎已经做完了?等等,还有个小问题,题意还要求半径最大。又该怎么办呢? 想想半径最大的是什么?是直线啊!那这题不让直线怎么办?那就尽可能的直!什么情况下能尽可能的直?**凸包上相邻的三个点**! 然后就真的做完了。 ## 代码 ```cpp 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; } ```