题解：P17040 [NWERC 2021] Dyson Circle

lailai0916 · 2026-08-31 01:01:30 · 题解

题意简述

平面上给出若干星星格。选择尽量少的单位格作为屏障，使所有星星位于同一个四连通有限区域内，并且该区域不能通过边与无限外部相连。屏障格之间只需至少共用一个角。

解题思路

使用旋转后的坐标：

原网格中的每个格子满足 u\equiv v\pmod2。两个原格子共边时，u,v 各改变 1；两个格子至少共用一个角时，则有：

记所有星星在 u 方向的极差为 X，在 v 方向的极差为 Y。答案主要由这两个数决定。

先证明下界。设某个方案的内部连通区域为 S，它在 u,v 方向的极差分别为 A,B。内部包含所有星星，所以 A\ge X、B\ge Y。

屏障的外边界中存在一条由不同屏障格组成的简单闭合链，记长度为 q。链中格子数不超过全部屏障格数。分别从 S 的四个坐标极值向外走到无穷远，必然穿过屏障，因此闭合链在两个方向的极差至少为：

沿闭合链走一周。任意坐标从最小值走到最大值并回到最小值，总变化量至少是极差的两倍。再利用相邻屏障格的坐标变化，可以得到：

所以任意方案至少需要：

还需处理退化情形。若 n>1 且 X=0，至少有两颗不同的星星位于同一条 u 对角线上。连接它们的四连通路径每走一步都会改变 u，所以内部区域不可能仍满足 u 极差为零，必有 A\ge1。此时下界变为 X+Y+5。当 Y=0 时结论对称。两种极差不会同时为零，否则所有星星都在同一个格子。

下面给出达到下界的构造。先在 (u,v) 平面取包含所有星星的最小轴对齐矩形，并只保留满足 u\equiv v\pmod2 的格点。这些格点与原网格格子一一对应。

当 X,Y>0 时，矩形内的合法格点构成四连通区域。取它在原网格中的全部外侧四邻格作为屏障，边界由四条单调阶梯链组成。沿两组坐标方向计数，屏障格数恰为：

若 n>1 且某个极差为零，矩形内的合法格点会沿对角线分离。把零极差的方向向任意一侧扩展一个单位后，内部变为四连通，屏障数量相应增加一，恰好达到 X+Y+5。若只有一颗星星，直接选择它的四个边相邻格即可。

因此最终答案为 X+Y+4；当 n>1 且 X=0 或 Y=0 时再加一。只需扫描全部星星的两个变换坐标，时间复杂度为 O(n)，空间复杂度为 O(1)。

正确性证明

任意可行屏障都包含围住内部区域的闭合外边界。闭合链在 u,v 两个方向必须分别跨过内部极值的外侧一层，坐标总变化量又至少为两个极差的两倍，所以屏障数量不小于 A+B+4，进而不小于 X+Y+4。若多颗星星在某个变换坐标上极差为零，四连通性迫使内部在该方向至少扩展一格，下界再增加一。

非退化时，变换坐标最小矩形中的合法格点构成四连通内部，其外侧四邻格形成一条闭合屏障，数量为 X+Y+4。退化时扩展一个单位后得到四连通内部与 X+Y+5 个屏障格；单颗星星则由四格包围。所有构造都达到对应下界，因此算法给出的数量最小。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int mn[2]={inf,inf};
    int mx[2]={-inf,-inf};
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        int v[2]={x+y,x-y};
        for(int j=0;j<2;j++)
        {
            mn[j]=min(mn[j],v[j]);
            mx[j]=max(mx[j],v[j]);
        }
    }
    int d[2]={mx[0]-mn[0],mx[1]-mn[1]};
    int ans=d[0]+d[1]+4;
    if(n>1&&(!d[0]||!d[1]))ans++;
    cout<<ans<<'\n';
    return 0;
}