题解：P17358 [ECNA 2024] Fences Make Good Neighbors

· · 题解

题意简述

给定一个凸 n 边形和内部两个不同的点。用互不相交的对角线将多边形剖分为三角形，要求两个点所在的三角形之间恰好隔着一个三角形，即从一个三角形到另一个三角形需要跨过恰好两条对角线。

任何对角线都不能经过这两个点。求所有新增对角线的最小长度和；不存在合法剖分时输出 IMPOSSIBLE。

解题思路

固定一种三角剖分，把每个三角形看成一个点，共用一条对角线的两个三角形之间连边，得到一棵树。原因是凸多边形的一条对角线会将其分成两个较小的多边形，两侧的三角形之间只能通过这条对角线相连；递归地看，每次都是将两棵树用一条边连接。

这棵树中，两个房屋所在三角形之间的路径长度应当为 2。直接在区间动态规划中维护这条路径不方便，但可以改为判断每条对角线是否将两个房屋分开。

设两个房屋为 b_0,b_1。对于对角线 (i,j)，计算叉积：

\begin{aligned} x & =(a_j-a_i)\times(b_0-a_i) \\ y & =(a_j-a_i)\times(b_1-a_i) \end{aligned}

若 x=0 或 y=0，这条对角线经过房屋，不能使用。这里利用了多边形的凸性：房屋位于多边形内部，而对角线所在直线与多边形的交集就是该对角线，因此房屋不可能只落在其延长线上。

否则，x,y 异号当且仅当两个房屋分处对角线两侧。删除这条对角线对应的树边，也恰好把两侧的三角形分开，所以它位于两个房屋之间的树上路径，当且仅当 x,y 异号。

因此，原要求等价于 整个剖分恰好使用两条将房屋分开的对角线。只需维护一个不超过 2 的计数，不必记录房屋具体位于哪个三角形。

按题目给定顺序将顶点编号为 1,2,\dots,n。设 c_{i,j} 表示线段 (i,j) 是否将两个房屋分开，是则为 1，否则为 0。

为了避免在合并时重复计算长度，将每个区间的闭合边也算入该区间。定义 d_{i,j}：如果 (i,j) 是原多边形的边，取 0；否则取其欧几里得长度。

令 f_{i,j,t} 表示剖分顶点 i,i+1,\dots,j 构成的子多边形，并将闭合边 (i,j) 计入后，分隔房屋的对角线总数为 t 时的最小费用。这里只保留 t=0,1,2。

相邻两个顶点之间没有三角形，也没有新围栏，因此 f_{i,i+1,0}=0，其余状态初始为无穷大。若闭合边经过房屋，则整个区间状态不可用。

对于至少包含三个顶点的区间，枚举与闭合边 (i,j) 相邻的三角形 (i,k,j)。它的另外两条边将剩余部分分成区间 [i,k] 和 [k,j]。两个子区间已经分别计算了闭合边 (i,k)、(k,j)，所以合并时只需额外加入 (i,j)：

f_{i,j,u+v+c_{i,j}}=\min\left(f_{i,j,u+v+c_{i,j}},f_{i,k,u}+f_{k,j,v}+d_{i,j}\right)

其中 i<k<j，且 u+v+c_{i,j}\le2。任何合法三角剖分都有唯一一个与 (i,j) 相邻的三角形，所以枚举不会遗漏；反过来，两侧子区间内部不相交，合法子剖分也一定能够与这个三角形合成合法剖分。

每条新增对角线恰好作为一个子区间的闭合边被计费一次。计数也只会在合并时相加，不会减少，因此舍去超过 2 的状态是安全的。

最终取 f_{1,n,2}。根区间的闭合边 (1,n) 本来就在多边形边界上，费用和分隔计数均为 0，不产生额外贡献。若该状态仍为无穷大，则无解。

代码将至多六种计数组合直接展开。时间复杂度为 O(n^3)，空间复杂度为 O(n^2)。叉积使用 long long 精确判断共线及两侧关系，只有长度计算使用浮点数。

参考代码

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

using ll=long long;
const int N=505;
const double inf=1e100;
struct Point
{
    int x,y;
}a[N],b[2];
double f[N][N][3],dis[N][N];
int cnt[N][N];
bool vis[N][N];
ll cross(Point a,Point b,Point c)
{
    return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    for(int i=0;i<2;i++)cin>>b[i].x>>b[i].y;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            ll x=cross(a[i],a[j],b[0]),y=cross(a[i],a[j],b[1]);
            vis[i][j]=x&&y;
            cnt[i][j]=(x<0)!=(y<0);
            dis[i][j]=hypot(a[i].x-a[j].x,a[i].y-a[j].y);
            if(j==i+1||i==1&&j==n)dis[i][j]=0;
            for(int k=0;k<3;k++)f[i][j][k]=inf;
            if(j==i+1)f[i][j][0]=0;
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=i+2;j<=n;j++)
        {
            if(!vis[i][j])continue;
            for(int k=i+1;k<j;k++)
            {
                int t=cnt[i][j];
                f[i][j][t]=min(f[i][j][t],f[i][k][0]+f[k][j][0]+dis[i][j]);
                f[i][j][t+1]=min(f[i][j][t+1],min(f[i][k][0]+f[k][j][1],f[i][k][1]+f[k][j][0])+dis[i][j]);
                if(!t)f[i][j][2]=min(f[i][j][2],min({f[i][k][0]+f[k][j][2],f[i][k][1]+f[k][j][1],f[i][k][2]+f[k][j][0]})+dis[i][j]);
            }
        }
    }
    if(f[1][n][2]>=inf/2)cout<<"IMPOSSIBLE"<<'\n';
    else cout<<fixed<<setprecision(10)<<f[1][n][2]<<'\n';
    return 0;
}