首页 > 其他 > 详细

codechef KTHCON

时间:2020-05-09 12:46:48      阅读:48      评论:0      收藏:0      [点我收藏+]

题意

给定点集,求子集构成的最大非凸多边形面积

做法

先做一遍凸包,若所有点都在凸包上则无解

否则答案一定是该凸包缺一个三角形的样子,问题转化为以凸包上一条边作为基底,另找凸包内一个点,最小化三角形面积

顺时针移动基底时,点也是顺时针移动的

然后有个小trick,就是内部点再求个凸包,然后类似旋转卡壳做就完了

codechef KTHCON

原文:https://www.cnblogs.com/Grice/p/12856253.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!