Facebook Hacker Cup
facobookHackCup是facebook下面的一個(gè)算法比賽封字，始于2011年疆柔，每年舉辦一屆刑顺。來(lái)自世界各地的coder都能夠參加該項(xiàng)比賽隶校。
在前兩天夺姑，HackCup剛進(jìn)行完資格賽的選拔。資格賽有三個(gè)題目穆桂，只要通過(guò)其中之一就可以獲得晉級(jí)宫盔。我們來(lái)看看資格賽的題目吧。今天先看第一題享完。
Progress Pie
題目
上圖是一個(gè)圓形進(jìn)度條飘言，P表示進(jìn)度的百分比，圓心為(50,50),邊長(zhǎng)為50驼侠，已經(jīng)加載的部分會(huì)被染成黑色姿鸿，現(xiàn)在給你一些數(shù)據(jù)，P表示百分比倒源，X,Y分別為橫縱坐標(biāo)苛预。判斷該點(diǎn)是白色還是黑色。
輸入樣例
輸出樣例
原題
思考
首先我們考慮2個(gè)特殊的情況：
1.P=0的情況笋熬，無(wú)論點(diǎn)在哪里都是白色热某。
2.點(diǎn)到圓心的距離大于50，那么點(diǎn)肯定不在圓內(nèi)胳螟，肯定也是白色昔馋。判斷公式為(x - 50) * (x - 50) + (y - 50) * (y - 50) > 2500
接下來(lái)，我們?cè)賮?lái)繼續(xù)討論這個(gè)問(wèn)題糖耸。
我們現(xiàn)在有兩種方式可以判斷第2個(gè)問(wèn)題
1.判斷叫AOB是否大于等于角AOC秘遏，注意到這個(gè)角可能大于180°
2.判斷線OC是否在線OA與OB之間。
這里我采用了第二種方式嘉竟，我們可以用叉積來(lái)判斷OC與OB的關(guān)系邦危，OC與OA的關(guān)系，從上圖看出舍扰，我們發(fā)現(xiàn)OC在OA的右手邊倦蚪，OC在OB的左手邊，但我們同時(shí)又注意到了边苹，因?yàn)檫@個(gè)角可能大于180度陵且，所以可能會(huì)存在這樣的問(wèn)題。
我們發(fā)現(xiàn)情況有好幾種个束，并不能簡(jiǎn)單地靠左手右手來(lái)進(jìn)行判斷慕购，而要對(duì)這個(gè)角是否超過(guò)180度進(jìn)行分類(lèi)討論，也就是P大于50%.
這里我用了另外一種stupid的方法播急，我把圓形切成1,2,3,4象限脓钾，如果C點(diǎn)所在象限小于B點(diǎn)，那么就肯定是Black桩警，反之則是White，如果相等再去判斷OC是否在OB的左邊昌妹。
部分代碼
