Facebook Hacker Cup 2017 Qualification Round - Progress Pie

問題

https://www.facebook.com/hackercup/problem/1254819954559001/

考察

基本的には角度を取って比較すれば良さそうに見えます。
0°の線を基準とした角度で図りますが、180°を超えると厄介なので素直に分けて考えます。
また、0°の線を挟んで反対側にPと点がある場合は、先に処理をしておくと楽になりそうです。

p進んだ時に描く円周上の点をPとします(最初は(50,100))。

Pと点が同じ側であれば、余弦定理を使うことで簡単にコサインが算出されるため、その大小を比較すれば良さそうです。


\displaystyle cosA = \frac{b^{2} + c^{2} - a^{2}}{2bc}

処理と例外

まず、中心が(50, 50)だと面倒なので、それぞれ-50をして中心が(0,0)になるようにします。
次に、中心からの距離が50より大きければ必ず円の外で白なので、これは先に処理します。

また、後の処理を簡単にするため、一色に定まったり判定が微妙になりそうな線上のケースを除外します。
誤差はある程度許容されるはずですが、怪しいところは削っておきます。

  • p==0の場合) 必ず白
  • p==100の場合) (距離の判定は事前にしているので)必ず黒
  • x==0 && y>=0の場合) (p!=0なので)必ず黒
  • x==0 && y<=0の場合) (距離の判定は事前にしているので)p >= 50かどうかでどちらかに決まる

さらに、反対側にある場合を処理します。

  • x>=0 && p>=50の場合) (距離の判定は事前にしているので)必ず黒
  • x<=0 && p<=50の場合) 必ず白

ここまでやると、あとは0°の直線を挟んで同じ側にある場合のみ処理すればよいです。

これはPと点のそれぞれでコサインの値を算出し、p<=50ならPの方が小さければ黒(先に行っている)、p>=50ならその逆になります。

コード

bool sovle() {
    int p, _x, _y;
    cin >> p >> _x >> _y;

    int x = _x - 50;
    int y = _y - 50;

    int dist = (x*x + y*y);
    if(dist > 50*50)
        return false;

    if(p == 0)
        return false;
    if(p == 100)
        return true;

    if(x == 0 && y >= 0)
        return true;
    if(x == 0 && y <= 0)
        return p >= 50;

    if(x >= 0 && p >= 50)
        return true;
    if(x <= 0 && p <= 50)
        return false;

    int dy = abs(y-50);
    int a2 = (x*x) + (dy*dy);
    double cosA = (double)(50*50 + dist - a2) / (2.0*50*sqrt(dist));

    double degP = 360.0 * p / 100;
    double cosP = cos ( degP * M_PI / 180.0 );

    if(p <= 50)
        return cosP <= cosA;
    else
        return cosA <= cosP;
}

int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        if(sovle())
            cout << "black" << endl;
        else
            cout << "white" << endl;
    }

    return 0;
}

感想

どこまで例外処理をしたらいいかがイマイチわからなくて、考え漏れがありそうななんだか厄介な問題でした。
コーナーケースがどっちになるか分かりにくくて辛いです。