CF575E Spectator Riots 题解

作者: xht37 分类: 题解 发布时间: 2020-02-20 21:04

点击数:111

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注