Visits: 351

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;
}