题解：P16127 [ICPC 2018 NAIPC] Cut It Out!

· · 题解

题意简述

凸多边形 B 严格位于凸多边形 A 内部。每次沿 B 的一条边所在的直线切开当前多边形，丢弃不包含 B 的部分，代价为切口长度。

求最终仅剩 B 时的最小总代价。

解题思路

每条切割直线都唯一对应 B 的一条边。由于 B 严格位于 A 内部，最终边界上的每条边都必须通过切割产生，因此所有边都要切一次。已经切过的直线不会再改变保留部分，也不需要重复切割，问题就是确定这些边的切割顺序。

将 B 的边按顺时针编号。若已经切过若干条边，考虑尚未切割的边 k，设它在环上最近的已切割前驱、后继分别为 l,r。计算边 k 的当前切口时，仅需要原多边形 A 和边 l,r 保留的两个半平面，不需要其余已切割边。

原因在于凸性。沿边 k 的直线，从这条边向两端延伸，超过某个已切割半平面后，这一侧的点就已经被丢弃。对于直线上的一个外部点，从该点看到的凸多边形边界是一段连续的边链；不包含这个点的保留半平面，也对应这条连续边链。从边 k 的一端延伸时，这条边链从该端相邻的边开始，沿环连续扩展。

因此，若这一侧的点被某条已切割边排除，这条可见边链必然包含该侧环上最近的已切割边，最近边的半平面也已经排除了它。另一侧同理。其余已切割边不能再缩短由 A,l,r 限制后的线段。这也覆盖相邻两条切线平行或交点位于 A 外部的情况：某一方向没有提供有效限制时，仍由 A 的边界限制。

这使尚未切割的边自然分成若干连续区间。定义 f_{l,r} 为边 l,r 已经切过，切完两者之间的全部边所需的最小附加代价，不包含边 l,r 自身的切割代价。若两边相邻，中间没有待切边，故 f_{l,l+1}=0。

设区间中首先切割边 k，当前代价记为 c(k,l,r)。切完后，剩余边分成 (l,k) 和 (k,r) 两个区间。由最近已切割边的性质，两个区间的后续切口相互独立，交错执行它们也不会改变代价，因此有：

f_{l,r}=\min_{l<k<r}(f_{l,k}+f_{k,r}+c(k,l,r))

任意切割顺序都有区间内的第一条边，所以转移不会漏掉最优解；反过来，先切枚举的边，再执行两个子区间的最优顺序，就能实现转移得到的代价。

下面计算 c(k,l,r)。设边 k 从点 P_k 指向 P_{k+1}，方向向量为 D_k=P_{k+1}-P_k。直线上的点用参数 t 表示为 P_k+tD_k，参数区间长度乘以 |D_k|，就是切口的实际长度。

输入顶点按顺时针给出，所以一条从点 Q 沿方向 E 的边，对应的保留半平面为 \operatorname{cross}(E,X-Q)\le 0。代入待切直线上的点，得到一元一次不等式：

\operatorname{cross}(E,P_k-Q)+t\operatorname{cross}(E,D_k)\le 0

记常数项为 u，t 的系数为 v。若 v>0，得到上界 t\le-u/v；若 v<0，得到下界 t\ge-u/v；若 v=0，两条直线平行。由于待切边属于 B，已经在所有保留半平面中，平行的半平面不会排除整条直线，也不提供参数上下界。

对每条待切边，先用 A 的全部边求出初始参数区间，保存在 lo 和 hi 中。再预处理每条 B 边施加的下界与上界，保存在 lmt 和 rmt 中，没有对应限制时用无穷界。每次转移将初始区间与边 l,r 的限制求交，便能在常数时间内得到切口长度。求交后仍包含边 k 本身，区间不会为空。

所有叉积都先使用整数计算。坐标差的绝对值不超过 2\times 10^6，叉积绝对值不超过 8\times 10^{12}，可以放入 long long，因此平行判定不依赖浮点误差。除法、长度和动态规划再使用 long double。

最后处理环。将边序列复制一份，并按区间长度从小到大计算。枚举第一条切割边 i，它的代价是这条直线在完整 A 中的长度；剩余所有边构成区间 (i,i+n)，两端实际对应同一条已切割边。加上 f_{i,i+n} 后取最小值，即为答案。代码访问几何数据时对边编号模 n，而动态规划仍使用展开后的下标。

设 A,B 的边数分别为 m,n，预处理需要 O(mn+n^2)，区间动态规划需要 O(n^3)，总时间复杂度为 O(mn+n^3)，空间复杂度为 O(n^2)。

参考代码

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

using ll=long long;
using ld=long double;
const int N=205;
const ld inf=1e30L;
struct P
{
    ll x,y;
    P operator-(P a){return {x-a.x,y-a.y};}
};
P a[N],b[N];
ld lo[N],hi[N],len[N],lmt[N][N],rmt[N][N],f[N*2][N*2];
ll cross(P a,P b){return a.x*b.y-a.y*b.x;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin>>m;
    for(int i=0;i<m;i++)cin>>a[i].x>>a[i].y;
    a[m]=a[0];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>b[i].x>>b[i].y;
    b[n]=b[0];
    for(int i=0;i<n;i++)
    {
        P d=b[i+1]-b[i];
        len[i]=sqrtl((ld)d.x*d.x+(ld)d.y*d.y);
        lo[i]=-inf;
        hi[i]=inf;
        for(int j=0;j<m;j++)
        {
            P e=a[j+1]-a[j];
            ll u=cross(e,b[i]-a[j]),v=cross(e,d);
            if(v>0)hi[i]=min(hi[i],-(ld)u/v);
            else if(v<0)lo[i]=max(lo[i],-(ld)u/v);
        }
        for(int j=0;j<n;j++)
        {
            lmt[i][j]=-inf;
            rmt[i][j]=inf;
            P e=b[j+1]-b[j];
            ll u=cross(e,b[i]-b[j]),v=cross(e,d);
            if(v>0)rmt[i][j]=-(ld)u/v;
            else if(v<0)lmt[i][j]=-(ld)u/v;
        }
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j+i<2*n;j++)
        {
            f[j][j+i]=inf;
            for(int k=j+1;k<j+i;k++)
            {
                int u=k%n,v=j%n,w=(j+i)%n;
                ld l=max({lo[u],lmt[u][v],lmt[u][w]}),r=min({hi[u],rmt[u][v],rmt[u][w]});
                f[j][j+i]=min(f[j][j+i],f[j][k]+f[k][j+i]+(r-l)*len[u]);
            }
        }
    }
    ld ans=inf;
    for(int i=0;i<n;i++)ans=min(ans,f[i][i+n]+(hi[i]-lo[i])*len[i]);
    cout<<fixed<<setprecision(12)<<ans<<'\n';
    return 0;
}