标签：int ConvexPolygonGame up second dw rep first

博弈 #计算几何

这要先手可以操作，那么一定存在必胜策略

所以题目转化为 判原来的多边形内有没有三个不共线的点

把所有点求出来判共线即可

// Author: xiaruize
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

int n;
pii a[N];
int up[N], dw[N];
vector<pii> vec;

void calc(pii x, pii y)
{
    if (x.first > y.first)
        swap(x, y);
    up[x.first] = max(up[x.first], x.second - 1);
    dw[x.first] = min(dw[x.first], x.second + 1);
    up[y.first] = max(up[y.first], y.second - 1);
    dw[y.first] = min(dw[y.first], y.second + 1);
    if (x.first == y.first)
        return;
    double k = (double)(y.second - x.second) / (double)(y.first - x.first);
    rep(i, x.first + 1, y.first - 1)
    {
        double j = (i - x.first) * k + x.second;
        debug(j);
        up[i] = max(up[i], floor(j));
        dw[i] = min(dw[i], ceil(j));
    }
}

void solve()
{
    cin >> n;
    rep(i, 1, n)
    {
        cin >> a[i].first;
        a[i].first += 1e5;
    }
    cin >> n;
    rep(i, 1, n) cin >> a[i].second;
    mms(up, -0x3f);
    mms(dw, 0x3f);
    a[n + 1] = a[1];
    rep(i, 1, n)
        calc(a[i], a[i + 1]);
    rep(i, 0, 2e5)
    {
        rep(j, dw[i], up[i])
        {
            vec.push_back({i, j});
            // debug(i, j);
            if (vec.size() > 2e5 + 1)
            {
                cout << "Masha" << endl;
                return;
            }
        }
    }
    if (vec.size() < 3)
    {
        cout << "Petya" << endl;
        return;
    }
    pii la = {vec[1].first - vec[0].first, vec[1].second - vec[0].second};
    rep(i, 2, vec.size() - 1)
    {
        pii cur = {vec[i].first - vec[0].first, vec[i].second - vec[0].second};
        if (cur.first * la.second - cur.second * la.first)
        {
            cout << "Masha" << endl;
            return;
        }
    }
    cout << "Petya" << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

标签：int,ConvexPolygonGame,up,second,dw,rep,first
From： https://www.cnblogs.com/xiaruize/p/18119844