标签：P4112DrawingPointsDivOne cur int rep cin 799 mid

二分

具有单调性，考虑二分答案

对于 \(x\) 考虑怎么 \(check\)，可以暴力的展开 \(x\) 次，再缩小 \(x\) 次，如果得到的结果和初始状态相同，那么就合法，否则不合法

// Author: xiaruize
const int N = 1e3 + 10;

int n;
pii a[N];
bool s[N][N], cur[N][N], mp[N][N];

bool check(int x)
{
    // debug(x);
    rep(i, 0, 799)
    {
        rep(j, 0, 799)
        {
            s[i][j] = false;
        }
    }
    rep(i, 1, n)
    {
        s[a[i].first + 400][a[i].second + 400] = true;
    }
    rep(asdasd, 1, x)
    {
        rep(i, 1, 799)
        {
            rep(j, 1, 799)
            {
                cur[i][j] = (s[i - 1][j - 1] | s[i - 1][j + 1] | s[i + 1][j - 1] | s[i + 1][j + 1]);
            }
        }
        rep(i, 1, 799)
        {
            rep(j, 1, 799)
            {
                s[i][j] = cur[i][j];
            }
        }
    }
    rep(asdads, 1, x)
    {
        rep(i, 1, 799)
        {
            rep(j, 1, 799)
            {
                cur[i][j] = (s[i - 1][j - 1] & s[i - 1][j + 1] & s[i + 1][j - 1] & s[i + 1][j + 1]);
            }
        }
        rep(i, 1, 799)
        {
            rep(j, 1, 799)
            {
                s[i][j] = cur[i][j];
            }
        }
    }
    rep(i, 1, 799)
    {
        rep(j, 1, 799)
        {
            if (s[i][j] && !mp[i][j])
                return false;
            if (!s[i][j] && mp[i][j])
                return false;
        }
    }
    return true;
}

void solve()
{
    cin >> n;
    rep(i, 1, n)
    {
        cin >> a[i].first;
        a[i].first *= 2;
    }
    cin >> n;
    rep(i, 1, n)
    {
        cin >> a[i].second;
        a[i].second *= 2;
        mp[a[i].first + 400][a[i].second + 400] = true;
    }
    int l = 0, r = 141;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    if (l >= 140)
    {
        cout << "-1" << endl;
        return;
    }
    cout << l << 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;
}

标签：P4112DrawingPointsDivOne,cur,int,rep,cin,799,mid
From： https://www.cnblogs.com/xiaruize/p/18121246