题解：P11473 名字取好了吗

先考虑如何对于所有 $i$ 求出 $f(1,i)$。

以下约定 $[x,y]$ 表示连接 $x$ 号点和 $y$ 号点的线段（这条线段不一定在原图上存在），若 $[x,y]$ 在原图上存在，记 $[x,y]_w$ 表示 $[x,y]$ 的权值。

设 $g_{l,r,0/1,0/1}$ 为满足以下条件的路径的最小代价：

初始设 $g_{1,1,0,0}=g_{1,1,1,0}=0$。可按照上述状态设计写出状态转移方程（转移方式较多，且转移时需要注意是否需要加上三角形面积）。由于图上线段数量与 $n$ 同级，故可以以 $\Theta(n^2)$ 的复杂度完成 dp，从而对于所有 $i$ 求出 $f(1,i)$。

接下来考虑分治。每条线段将凸包分为两个部分，我们找到按线段分割后两个部分点数最小值最大的线段，对于一个规模为 $n$ 的问题，可以证明按找到的线段分割后，点数较少的部分的点数至少为 $\lceil\frac{n}{3}\rceil+1$。

具体证明过程如下：首先可以将凸包拉成一个正多边形，不改变线段间的相交关系，凸包被线段分为若干个三角形，找到包含正多边形外接圆的圆心的三角形（若圆心在线段上，则可以任选一个包含这条线段的三角形），该三角形的三条边所对的弧的长度均不超过外接圆周长的一半，这些弧上的点数之和为 $n+3$（有 $3$ 个点被重复计算两次），最长的弧至少包含了 $\lceil\frac{n+3}{3}\rceil=\lceil\frac{n}{3}\rceil+1$ 个点，按该弧所对应的线段分割，即可得到一个点数较小的部分的点数至少为 $\lceil\frac{n}{3}\rceil+1$ 的分割方案。

于是我们可以按一条线段将凸包分割为两个凸包，使得点数较少的部分的点数至少为 $\lceil\frac{n}{3}\rceil+1$，点数较多的部分的点数至多为 $n-\lceil\frac{n}{3}\rceil+1$。

分割凸包后，我们记这两部分的点集为 $L$ 和 $R$，分割凸包的线段为 $[u,v]$（$u$ 和 $v$ 同时在 $L$ 和 $R$ 中）。现在需要求满足 $i\in L$ 且 $j\in R$ 且 $i,j\not\in\{u,v\}$ 的点对 $(i,j)$ 对答案的贡献。设 $h_{u/v,L/R,0/1,i}$ 表示以 $u/v$ 为起点，只经过 $L/R$ 中的点，不经过/经过 $[u,v]$，终点为 $i$ 的最小代价。可以通过之前的 dp 以 $\Theta(n^2)$ 的时间复杂度求出所需的 $h$。

则：

于是我们以 $\Theta(n^2)$ 的时间复杂度求出了所有满足 $i\in L$ 且 $j\in R$ 且 $i,j\not\in\{u,v\}$ 的点对 $f(i,j)$。接下来考虑递归计算求 $L$ 内部和 $R$ 内部的点对对答案的贡献。递归计算 $L$ 部分的过程中，需要考虑从 $u$ 到 $v$ 可以经过 $R$ 中的点，于是可以通过 $h_{u,R,0,v}$ 来更新 $[u,v]$ 的权值，但注意这需要与原权值分开记录，因为不直接通过 $[u,v]$ 的路径可能会影响 $L$ 部分纯净三角形面积的计算。对于递归计算 $R$ 部分的过程同理。

总体时间复杂度 $T(n)=T(\frac{2n}{3})+T(\frac{n}{3})+\Theta(n^2)$，可计算得总体时间复杂度为 $\Theta(n^2)$。