来自Facebook算法比赛的题目(一)

Facebook Hacker Cup

facobookHackCup是facebook下面的一个算法比赛,始于2011年,每年举办一届。来自世界各地的coder都能够参加该项比赛。

在前两天,HackCup刚进行完资格赛的选拔。资格赛有三个题目,只要通过其中之一就可以获得晋级。我们来看看资格赛的题目吧。今天先看第一题。

Progress Pie

题目

来自Facebook算法比赛的题目(一)

上图是一个圆形进度条,P表示进度的百分比,圆心为(50,50),边长为50,已经加载的部分会被染成黑色,现在给你一些数据,P表示百分比,X,Y分别为横纵坐标。判断该点是否已被加载,即白色还是黑色。

输入样例

来自Facebook算法比赛的题目(一)

输出样例

来自Facebook算法比赛的题目(一)

原题

来自Facebook算法比赛的题目(一)

思考

首先我们考虑2个特殊的情况:

1.P=0的情况,无论点在哪里都是白色。

2.点到圆心的距离大于50,那么点肯定不在圆内,肯定也是白色。判断公式为(x - 50) (x - 50) + (y - 50) (y - 50) > 2500

接下来,我们再来继续讨论这个问题。

来自Facebook算法比赛的题目(一)

我们现在有两种方式可以判断第2个问题

1.判断叫AOB是否大于等于角AOC,注意到这个角可能大于180°

2.判断线OC是否在线OA与OB之间。

这里我采用了第二种方式,我们可以用叉积来判断OC与OB的关系,OC与OA的关系,从上图看出,我们发现OC在OA的右手边,OC在OB的左手边,但我们同时又注意到了,因为这个角可能大于180度,所以可能会存在这样的问题。

来自Facebook算法比赛的题目(一)

我们发现情况有好几种,并不能简单地靠左手右手来进行判断,而要对这个角是否超过180度进行分类讨论,也就是P大于50

来自Facebook算法比赛的题目(一)

这里我用了另外一种stupid的方法,我把圆形切成1,2,3,4象限,如果C点所在象限小于B点,那么就肯定是Black,反之则是White,如果相等再去判断OC是否在OB的左边。

部分代码

来自Facebook算法比赛的题目(一)

个人资料
sam
等级:6
文章:18篇
访问:3.5w
排名: 20
推荐圈子
上一篇: 开源图计算框架GraphLab介绍
下一篇:来自Facebook算法比赛的题目(二)
猜你感兴趣的圈子:
每日一算法
标签: oc、ob、资格赛、oa、白色、面试题
隐藏