阿里 城堡问题求解答

题目:

将军大胜归来,夺取许多城堡(xi,yi)。国王许可,你站在任意的城堡上,选择任意视角,看得见的城堡都是你的,包括你站的城堡,但头不能动。而且你不能站在城堡构成的凸焦点上。将军的视角刚好小于180度(无限接近180度),可以看得无限远。请计算出将军最多能得多少城堡。如果所有的城堡都在凸焦点上,那么将军一个城堡也得不到。

输入:

第一行,整数m,表示接下来有m行。接下来的m行,每行都有2个数,表示一个城堡的坐标。

输出:

最多获得的城堡个数。

输入范例:

5

0 0

0 2

1 0

1 2

0.2 1.8

输出范例:

4

#阿里巴巴#
全部评论
本质上是画一条线,这条线经过至少一个非凸点,将线两边的点的数量最大化。
点赞 回复 分享
发布于 2017-08-22 01:28

相关推荐

大摆哥:刚好要做个聊天软件,直接让你帮他干活了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务