https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/barrier-protection
前提知識
解説
かなり自由に直線が引けるので、頂点を囲う三角形を作ればよさそう。
よって、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; } }