`算法题解` `AcWing` 4605. 最大周长

题目链接

相同的题

题解

前提知识: 多边形,凸多边形

前提知识: 笛卡尔坐标系, 边长与边权, 曼哈顿距离, 欧几里得距离,外接矩形

---

注意, 题中图里的第三个图形, 他是多边形!!! ; 因为他的边是直的,
但是, 此时他已远不止4个点, 而我们要求的是: 根据4个顶点, 得到一个4边形; 这样画法是个> 4边形;
其实这样的画法还有一个名字: 曼哈顿度量的多边形; 即两点间的距离, 用若干条 垂直/水平的线段 代替;
… 虽然, 这种画法的4边形是非法的; (但是… 这是本题一个故意迷惑人的一点…
… … 虽然这样画法的4边形是错误的, 即, 你在本题 遇到两点距离 肯定不会转换为这种画法(即曼哈顿度量)
… … 但是, 本题的解法, 必须要借助(曼哈顿度量), 即, 确实要转换为 (这种错误画法的 4边形)…

---

本题的边长不是(欧几里得距离), 是(曼哈顿距离)…
这好像感觉是挺(奇怪 矛盾)的…
这个多边形是在笛卡尔坐标系里, 他的每个边 在(坐标系)的长度, 肯定是(欧几里得距离);
但是, 我们硬生生的把这个(欧几里得距离), 去改变它 规定它的距离是 (曼哈顿距离)…

如果题中说, 它的(边权) 是 曼哈顿距离, 这样比较容易理解;
因为在该题中, 边长 与 边权, 确实是不同的两个概念, 因为比如任意两点(1,1) (2,2), 则它的边长 (在直角坐标系的长度) 就是$\sqrt{2}$
它的边权是 (曼哈顿距离)$1+1=2$, 这没有问题;

但本题非要说: 两点的边长distance 是 (曼哈顿距离); 也就是(边长为$2$);
那么, 你要想让这个边长 在坐标系里的长度, 确实是$2$, 那么, 这两个(1,1) (2,2) 就肯定不在这个位置了…

但是, 它非要说是(边长)… 也没办法, 但我们最好还是区分开:
边长是固定的它根据端点的坐标确定, 边权是可以自定义的, 本题的周长 其实是说的(边权)的周长

---

给定N个点的 (凸多边形), 其顺/逆时针方向 的 线性序列为: V0, V1, V2, ...

令Gi为在 该N凸边形的基础上, 任意的去掉N - i个点 后的 线性序列 所表示 i凸边形
根据去除若干点, 仍为凸多边形, 可以知道, 该多边形 也是 凸边形;

令两点间的边权为: 曼哈顿距离, 令多边形的周长为: 所有边权之和
则, 求G3, G4, ..., GN这些凸多边形的 最大的 曼哈顿周长Pi; N = 1e7, G是 Polygon P为Perimeter

凸多边形的曼哈顿周长, 等于: 其外接矩形的欧几里得周长;
因此, 以下我们研究某个凸多边形的曼哈顿周长, 都是转换为: 研究其外接矩形的欧几里得周长;

对于GN的周长PN, 我们知道, 其等于 外接矩形的周长;
令GN的外接矩形 的临界点Vl, Vu, Vr, Vd, 我们知道, 这4个点 就可以完全确定 外接矩形; (这4个点, 很容易求出)
此时, PN = 外接矩形的周长 = 2 * (Vr.x - Vl.x) + 2 * (Vu.y - Vd.y)

对于G(N-1)的周长P(N-1), 我们可以去掉 非Vl, Vu, Vr, Vd临界点 的其他任意点后, 此时的G(N-1)
它的外接矩形, 仍然是Vl, Vu, Vr, Vd, 即其P(N-1) = PN

因此, 对于P4, P5, ..., PN 其答案, 均为PN

---

但是关键是P3;

我们知道, 这4个临界点, 是针对(外接矩形)而言的, 因为矩形有4条边, 所以对应4个临界点;
而, 临界点 可能会重合, 比如, Vl 和 Vu都在 外接矩形的 左上角; 即, 一个多边形上的点, 对应2个临界点 (不会对应>=3, 因为外接矩形面积> 0)
但是, 临界点 它的本质 又是指的是(多边形的点), 因为临界点 一定是 (多边形的点), 不是 ( 外接矩形的顶点)

即, 对Vl, Vu, Vr, VD进行 (去重处理)后, 其点数 是{2 或 3 或 4}

---

假如去重后的点数是2 或 3, 则 对于G3, 它的三个顶点 就选择到 这些去重后的 临界点, 即, 其外接矩阵M 与 PN的一样
即, 此时P3 == PN

但是, 如果去重后的点数是4 (即, 4个临界点 都在 外接矩形M 的四条边上, 不在顶点处),
此时, 由于G3只有3个点, 无法选择这4个点, 因此, G3的外接矩形 一定小于 GN的外接矩形M (周长面积都小于)

但是, 我们可能很容易会认为: G3的三个端点, 一定是通过 选择这4个临界点中的任意3个, 可以实现;
… 不要理想当然…, 需要证明呀!

假设N凸多边形, 其外接矩形 由4个不同的点确定, 且外接矩形是个正方形; (假设正方形边长为2)

对于任意一个Gi (i >= 4)凸多边形, 其只要选择了Vl, Vu, Vr, Vd这4个临界点, 则该凸多边形的曼哈顿周长, 一定为 (绿色外接矩形的周长), 这是最大的;
而对于G3凸多边形(即三角形), 它的三个点, 如果从这4个临界点中选择3个, 则其该G3的外接矩形, 一定是2 + 2 + 1 + 1 = 6

但是, 如果我们选择Vl, Vu, Va (Va不是临界点), 可以看出, 它的外接矩形(橙色), 是大于6的

因此, 一定不要(理想当然)…

---

对于G3的情况, 确实要单独的分析;
上图中, 答案是: 两个点是临界点, 另外一个点是(其他点)
那么我们就尝试证明: G3的答案, 其端点中 至少含有2个临界点;

错误思路

令N边形的周长为 P1 (perimeter)
从 (N边形) 到 (N-1边形) 的过程, 枚举每个点, 刨去这个点后 的 N-1边形的 周长为P2
则, 最终的答案N-1边形周长, 一定是 最大的P2;

也就是, 每一次 刨去一个点;
在这一步, 这确实是正确的; 因为, 刨去a点后, N-1边形的周长最大;
但是, 你能保证: N - k边形里, 一定没有a点吗???

一定要意识到, 你这个算法, 是贪心的!!! 你必须保证: 无后效性, 事实上是做不到的;

从N -> (N-1) -> (N-2) -> …的过程, 并不是: 每次扔掉一个点;

无法证明贪心的合法性(即无后效性), 就不可以: 冒险尝试贪心!