平面上的凸包计算

摘要

cqvip:在郊野公园中有一片林地,生长着一些古老的树木。管理部门希望建围栏把这些树木围起来加以保护。为了便于外围修建步行道,方便游人观赏,将保护区设计成凸多边形。当然也希望围栏总长度尽可能小,以降低建设成本。为简化计算,我们假设可以用部分树木作为围栏的桩柱,换句话说,部分树木处于保护区域的边界上。图1是这个问题的示意图,左边标出树木的平面位置分布,右边则显示完成的围栏,位于围栏上的树木用空心点表示,围在内部的为灰色点。