还是要有梦想的 level
获赞
795
粉丝
6
关注
2
看过 TA
7
东南大学
2018
C++
IP属地:未知
暂未填写个人简介
私信
关注
2017-08-26 11:41
已编辑
东南大学 C++
0 点赞 评论 收藏
分享
2017-07-18 11:54
已编辑
东南大学 C++
题目:     将军大胜归来,夺取许多城堡( xi,yi )。国王许可,你站在任意的城堡上,选择任意视角,看得见的城堡都是你的,包括你站的城堡,但头不能动。而且你不能站在城堡构成的凸焦点上。将军的视角刚好小于 180 度(无限接近 180 度),可以看得无限远。请计算出将军最多能得多少城堡。如果所有的城堡都在凸焦点上,那么将军一个城堡也得不到。    输入 :    第一行,整数 m ,表示接下来有 m 行。接下来的 m 行,每行都有 2 个数,表示一个城堡的坐标。    输出 :    最多获得的城堡个数。    输入范例 :    0 0   0 2   1 0   1 2   0.2 1...
liuchang93:我也是这道题,也没做出来,我当时的思路是先求凸包上的点,然后穷举剩下所有点中每两点连成的直线,找线两侧存在的最大点数。。。不过这样复杂度好高,代码量也好多,没信心能写完,也确实没写完。后来和同学讨论,同学给的方法是基于jarvis步进法做改进,找夹角第二小的点,复杂度能到O(kn)。
投递阿里巴巴集团等公司10个岗位 >
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客企业服务