Barrier Protection [EEIC Programming Contest #0 A]

https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/barrier-protection

前提知識

• 幾何の知識

解説

https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/barrier-protection/submissions/code/1318657703

かなり自由に直線が引けるので、頂点を囲う三角形を作ればよさそう。
よって、3つあれば、必ず守れる。
いや、直線2つでもいけるな。
いける。
よって、あとは直線1つで身を守れるかを判定すればいい。
これは、2通りの方法がある。

1つ目は、凸包と多角形と点の包含関係を使う方法。
敵で凸法を作成したときに、その凸包に原点が含まれるかを判定する。
含まれないのであれば、直線を1つ引くことで原点を全ての敵を分離させることができる。
2つの機能のライブラリが必要となるが、既に持っている場合は。こちらで通すのが早い。

2つ目は、偏角を利用する方法。
原点から各敵について偏角を求める。
全ての偏角がある、180°の範囲に収まっていれば、直線で分離可能である。
偏角を求める部分はライブラリで持っておけばいいが、180°に収まるかの判定が少し大変。
ソートして尺取りとか、いろいろな工夫が必要になると思う。

//---------------------------------------------------------------------------------------------------
void _main() {
    int N;
    cin >> N;

    if (N == 1) {
        cout << 1 << endl;
        return;
    }
    else if (N == 2) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

        if (intersectSP(L(P(x1, y1), P(x2, y2)), P(0, 0))) {
            cout << 2 << endl;
        }
        else {
            cout << 1 << endl;
        }
        return;
    }

    G convex;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        convex.push_back(P(x, y));
    }

    convex = convex_hull(convex);

    if (contains(convex, P(0, 0)) == OUT) {
        cout << 1 << endl;
    }
    else {
        cout << 2 << endl;
    }
}