洛谷 P14944 已经没有什么好构造的了 题解

Solution

不难发现，凸多边形最多有 \(3\) 个锐角。因此对于 \(m>3\) 显然无解。否则分讨 \(m\) 的取值，构造方法如下图所示，红线代表一段凸壳。

这样问题就变成了如何构造红色的凸壳部分。由于只能用整点，因此凸壳中线段斜率均为有理数。
这启发我们构造一串不同的正斜率并从大到小排序。具体做法就是枚举所有满足 \(1\le p,q\le K\) 的 \(\frac{p}{q}\)，约分，排序并去重。发现 \(K=406\) 时就能得到至少 \(10^5\) 个不同斜率。

我们还需要证明这样做不会超出 \(10^8\) 的值域限制。由于凸壳中不超过 \(n\) 条线段，每条线段对 \(x,y\) 坐标的贡献均 \(\le K\)，因此右上角的点的 \(x,y\) 坐标均不会超过 \(nK\le 4.06\times 10^7

鼓励转贴优秀软件安全工具和文档！

前排留名，哈哈哈

新版吗？好像是停更了吧。

收藏一下   不知道什么时候能用到

用心讨论，共获提升！

感谢发布原创作品，程序园因你更精彩

谢谢分享，试用一下

用心讨论，共获提升！

懂技术并乐意极积无私分享的人越来越少。珍惜

热心回复！

收藏一下   不知道什么时候能用到

谢谢分享，辛苦了