如何使用凸包概念来解决这个问题

Question

我正在解决这个SPOJ problem，它使用了凸包的概念。

通过上面的link完全理解问题

如果这个问题稍微改变一下，给定一个点 A(x,y) 并要求我们仅在该特定点周围找到最大数量的围栏。

我的方法

（如有错误请指正）

1.FindN个点可以形成的不相交、不接触的凸包的最大个数（在问题中给定）

2.Find 点 A 位于其中的外壳数。

请帮我解决这个问题??

P.S. :- 我找不到任何类似的问题来验证我的方法。如果你发现 任何类似的问题请附在下面。

谢谢。

Answer 1

您的方法很有效。你的问题和SPOJ问题都可以递归考虑如下。

给定一组极点：

1. 确定最佳可能的最外层围栏
2. 用那个栅栏里面的电线杆再次解决问题

请注意，为问题添加另一个极点永远不会导致更糟糕的结果，因为您始终可以不使用它。

因此，在步骤 (1) 中，可用极点的凸包 总是 一个有效的选择，因为它里面的极点集是剩余极点的超集在任何其他选择之后。对于您的问题，如果有任何其他选择，它也会包含点 A。