HDU 5299 Circles Game

偏执的太偏执、 2021-12-22 08:11 195阅读 0赞

[HDU 5299][]

思路：

圆扫描线+树上删边博弈

圆扫描线有以下四种情况，用set维护扫描线与圆的交点，重载小于号

![1130834-20190402205314952-1884259873.png][]

代码：

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<bits/stdc++.h>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    
    const int N = 2e4 + 5;
    int nowx;
    struct circle {
        int x, y, r;
    }p[N];
    double Y(int id, int ty) {
        if(ty == 0) return p[id].y - sqrt(p[id].r*1.0*p[id].r - (nowx-p[id].x)*1.0*(nowx-p[id].x));
        else return p[id].y + sqrt(p[id].r*1.0*p[id].r - (nowx-p[id].x)*1.0*(nowx-p[id].x));
    }
    struct node {
        int id, ty;
        bool operator < (const node &rhs) const {
            if(id == rhs.id) return ty < rhs.ty;
            else return Y(id, ty) < Y(rhs.id, rhs.ty);
        }
    };
    set<node> s;
    vector<int> g[N];
    int T, n, dp[N], fa[N], sg[N];
    piii t[N*2];
    void dfs(int u, int o) {
        sg[u] = 0;
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if(v != o) {
                dfs(v, u);
                sg[u] ^= sg[v] + 1;
            }
        }
    }
    int main() {
        p[0].x = p[0].y = 0;
        p[0].r = 100000;
        s.insert({
         0, 0});
        s.insert({
         0, 1});
        scanf("%d", &T);
        while(T--) {
            scanf("%d", &n);
            for (int i = 1; i <= n; ++i) scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].r);
            for (int i = 1; i <= n; ++i) {
                t[i].fi.fi = p[i].x - p[i].r;
                t[i].fi.se = 0;
                t[i].se = i;
                t[n+i].fi.fi = p[i].x + p[i].r;
                t[n+i].fi.se = 1;
                t[n+i].se = i;
            }
            sort(t+1, t+1+2*n);
            for (int i = 1; i <= 2*n; ++i) {
                nowx = t[i].fi.fi;
                int id = t[i].se;
                node tmp = {id, 1};
                if(t[i].fi.se == 0) {
                    auto l = s.lower_bound(tmp); --l;
                    auto r = s.upper_bound(tmp);
                    if((*l).id == (*r).id) {
                        dp[id] = dp[(*l).id] + 1;
                        fa[id] = (*l).id;
                    }
                    else if(dp[(*l).id] >= dp[(*r).id]) {
                        dp[id] = dp[(*l).id];
                        fa[id] = fa[(*l).id];
                    }
                    else {
                        dp[id] = dp[(*r).id];
                        fa[id] = fa[(*r).id];
    
                    }
                    g[fa[id]].pb(id);
                    s.insert({id, 1});
                    s.insert({id, 0});
                }
                else {
                    s.erase({id, 1});
                    s.erase({id, 0});
                }
            }
            dfs(0, 0);
            if(sg[0]) printf("Alice\n");
            else printf("Bob\n");
            for (int i = 0; i <= n; ++i) g[i].clear(), sg[i] = fa[i] = dp[i] = 0;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/widsom/p/10645260.html

[HDU 5299]: https://cn.vjudge.net/problem/200194/origin
[1130834-20190402205314952-1884259873.png]: /images/20211220/8b49e56c090e459ab193d7264d2c09d7.png