首页 > 代码库 > poj 1228 Grandpa's Estate (稳定凸包问题)
poj 1228 Grandpa's Estate (稳定凸包问题)
---恢复内容开始---
题意:你的长辈给你留了块土地,然而这块土地是以一些钉子来界定的,题目要做的就是给你一堆钉子的坐标(也就是凸包上部分的点),然后问你能不能唯一确定这块土地
//不得不说知道题意后一脸懵逼。。
知识:稳定凸包
所谓稳定就是判断能不能在原有凸包上加点,得到一个更大的凸包,并且这个凸包包含原有凸包上的所有点。
举一个不稳定的例子
为什么说它不稳定呢?因为他可以加点来得到更大的凸包
那什么样子是稳定的呢?
因此我们可以知道当一个凸包稳定时,凸包的每条边上都要有至少三个点,若只有两个点,则可以增加一个点,得到更大的凸包。
现在我们反过来再看这道题就会发现非常easy了
代码实现:
---恢复内容结束---
poj 1228 Grandpa's Estate (稳定凸包问题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。