Facebook Hacker Cup
facobookHackCup是facebook下面的一个算法比赛,始于2011年,每年举办一届。来自世界各地的coder都能够参加该项比赛。
在前两天,HackCup刚进行完资格赛的选拔。资格赛有三个题目,只要通过其中之一就可以获得晋级。我们来看看资格赛的题目吧。今天先看第一题。
Progress Pie
题目
上图是一个圆形进度条,P表示进度的百分比,圆心为(50,50),边长为50,已经加载的部分会被染成黑色,现在给你一些数据,P表示百分比,X,Y分别为横纵坐标。判断该点是否已被加载,即白色还是黑色。
输入样例
输出样例
原题
思考
首先我们考虑2个特殊的情况:
1.P=0的情况,无论点在哪里都是白色。
2.点到圆心的距离大于50,那么点肯定不在圆内,肯定也是白色。判断公式为(x - 50) (x - 50) + (y - 50) (y - 50) > 2500
接下来,我们再来继续讨论这个问题。
我们现在有两种方式可以判断第2个问题
1.判断叫AOB是否大于等于角AOC,注意到这个角可能大于180°
2.判断线OC是否在线OA与OB之间。
这里我采用了第二种方式,我们可以用叉积来判断OC与OB的关系,OC与OA的关系,从上图看出,我们发现OC在OA的右手边,OC在OB的左手边,但我们同时又注意到了,因为这个角可能大于180度,所以可能会存在这样的问题。
我们发现情况有好几种,并不能简单地靠左手右手来进行判断,而要对这个角是否超过180度进行分类讨论,也就是P大于50
这里我用了另外一种stupid的方法,我把圆形切成1,2,3,4象限,如果C点所在象限小于B点,那么就肯定是Black,反之则是White,如果相等再去判断OC是否在OB的左边。
部分代码