P10860 Lili Likes Polygons 题解
本题来源是 Gym 105139C，官方题解链接。这是本场的防 AK 题，当然也是道思路很巧妙的网络流建模问题。
我们考虑对多边形
约定：记 ∟ 表示直角，2∟表示平角，3∟ 表示凹角（270°的角）。
引理 1：分割线与原图形的边不重合。证明显然。
引理 2：每条分割线的两个端点至少有一个是 3∟，并且没有一个是 ∟。
如果端点是 ∟，那么必然与原图形的边重合，不符合结论 1。那么剩下两个端点的情况就是：两个 2∟、一个 3∟ 一个 2∟、两个 3∟。
如果两个端点均为 2∟，容易发现这条分割线没有意义。即对于任意一组包含这条分割线的合法划分，去掉这条分割线仍然合法。除掉这种情况，剩下的情况中至少有一个端点为 3∟。
引理 3：任意两条分割线，要么不交，要么交于端点。
考虑平行于垂直两种情况。平行必然不交，垂直的话，两条分割线构成了一个十字形，可以发现这个十字形的四边必然存在一边是毫无必要的，把那条边去掉，答案不会更劣。
假设我们已经得知了一组合法划分，我们怎么计算出划分了有多少个矩形呢？我们可以使用内角和计算。划分后图形的内角和除以 4∟ 就是矩形数量。
但是我们在划分的过程中会让原图形的内角和改变，具体而言：
- 分割 2∟：内角和增大了 2∟
- 分割 3∟ 一次：内角和减小了 2∟
- 分割 3∟ 两次：内角和不变
考虑前面所说的分割线的两种情况：
- 分割 2∟ 和 3∟，内角和不受影响。
- 分割 3∟ 和 3∟，内角和减少了 4∟。
值得注意的是，3∟ 被分割后会变成 2∟。
我们称端点为 3∟ 的分割线是好分割线。
引理 4：任意合法分割内角和减少量等于不相交的好分割线条数乘以 4∟。
合法方案的必要条件：所有 3∟ 都至少被分割一次。
如果 3∟ 被好分割线分割，那么必然可以带来 2∟ 的贡献。那么这些不相交好分割线每条就会带来 4∟ 的贡献。对于其它没有被好分割线分割的 3∟，从它连出去的分割线必然无法分割另一个 3∟，只能分割 2∟。而这些分割线不会对答案产生影响。
于是做法就显而易见了：离散化，求出多边形的内角和。
对于每个 3∟，它在水平方向和竖直方向各至多有一个 3∟ 与其匹配，换言之，每个 3∟ 的水平 / 竖直好分割线都只有一条。我们把这些好分割线看作点，经过公共点的水平好分割线与竖直好分割线连边（只能选一条），可以建成一张二分图，不相交的好分割线条数 = 最大独立集 = 二分图总点数 - 最大匹配。
这张二分图的点数是原多边形的点数级别的，需要用最大流进行匹配。最后用原多边形内角和除以 4∟ 再减去最大独立集就是答案。