如何利用凸壳概念来解决这个问题。

Question

我在解决这个问题 SPOJ问题 其中使用了凸壳的概念。

通过上面的链接来完全理解这个问题。

如果这个问题稍微改变一下，给我们一个点，比如说A(x,y)，要求我们只在这个点周围找到最大的栅栏数。

我的方法

谬误

1.求由N个点(给定问题)所能形成的不相交,不相触的凸面体的最大数目

2.求点A位于其内部的船体的数量。

请帮我如何解决这个问题？

P.S. :-我找不到任何类似的问题，所以我可以验证我的方法。If you findany similar problem do attach below.

谢谢。

Answer 1

你的方法很好用。 你的问题和SPOJ问题都可以按以下方式递归考虑。

给定一组极点。

1. 确定最外侧的最佳栅栏
2. 再解决那个栅栏里面的杆子的问题。

请注意，在问题中增加另一个极点绝不会导致更坏的结果，因为你总是可以不用它。

所以，在步骤(1)中，可用极点的凸壳是 始终 是一个有效的选择，因为它里面的极点集是任何其他选择后剩余极点的超集。 对于你的问题，如果有其他选择，它也会包围点A。