問題一覧 > 通常問題

No.3008 ワンオペ警備員

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
0 ProblemId : 11792 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-01-17 21:49:17

問題文

く○けんご君は、美術館の設計を任されました。く○けんご君は、NN 個の 相異なるxyxy-座標平面の格子点 Pn=(Xn,Yn)P_n = (X_n, Y_n)P1,,PN,P1P_1, \dots, P_N, P_1 の順に線分で結んだ折れ線の形の設計図を書きました。
線分 PnPn+1\overline{P_n P_{n+1}}lnl_n とおきます(1nN, PN+1:=P11 \leq n \leq N, \ P_{N+1} := P_1)。異なる二つの線分 ln,lml_n, l_m が端点以外で交わるとき、「自己交差する」といい、ある連続する三点 Pn1,Pn,Pn+1 (1nN, P0:=PN)P_{n-1}, P_{n}, P_{n+1} \ (1 \leq n \leq N, \ P_0 := P_N) が同一直線上にあるとき、「無駄な点がある」といいます。
この設計図の折れ線図形が自己交差するか、あるいは無駄な点がある場合は 0 と出力してください。
そうでない場合、すなわち折れ線図形の設計図が多角形になる場合を考えます。けんご君は設計に予算を使いすぎたため、警備員を一人しか雇えません。この美術館のいずれかの頂点 PnP_n に警備員を一人だけ配置して、美術館の内部全体を死角なく監視できるかどうかを考えます。すなわち、適当な PnP_n を選べば、多角形の全ての点 QQ(内部の他に、辺上や頂点も含みます)について、線分 PnQ\overline{P_n Q} が多角形に含まれるようにできるなら 1 と出力し、できないときは -1 と出力してください。
判定条件が複雑なため、全てのサンプルに目を通すことをおすすめします。

入力

NN
X1 Y1X_1 \ Y_1
\vdots
XN YNX_N \ Y_N

3N103,3 \leq N \leq 10^3,
109Xn,Yn109 (n=1,,N).-10^9 \leq X_n, Y_n \leq 10^9 \ (n = 1, \dots, N).
ただし、P1=(X1,Y1),,PN=(XN,YN)P_1 = (X_1, Y_1), \dots, P_N = (X_N, Y_N) は反時計回りに並んでいるとは限りません。

出力

最後に改行してください。

サンプル

サンプル1
入力
5
-1 0
1 0
1 1
0 0
-1 1
出力
0


(0,0),(1,1)(0, 0), (-1, 1) を結ぶ線分と (1,0), (1,0)(-1, 0), \ (1, 0) を結ぶ線分は、後者の端点でない点で交わるので、自己交差します。そのため 0 が出力されます。

サンプル2
入力
5
1 100
0 0
-1 100
-1 -1
1 -1
出力
1


原点から五角形全体をくまなく監視できるので、1 が出力されます。

サンプル3
入力
6
0 0
3 0
2 3
2 1
1 1
0 2
出力
-1


この六角形はどの頂点に立っても監視できない死角が生まれる図形であり、-1 が出力されます。

サンプル4
入力
8
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0
出力
-1


漢字の「凹」のような形をした多角形であり、どこに立っても死角が生まれるため、-1 が出力されます。このサンプルでは頂点の順番は反時計回りではないことに注意してください。

サンプル5
入力
4
0 0
0 1
0 2
1 1
出力
0

最初の三つの点が同一直線上にあるため、無駄な点があり、0 が出力されます。

サンプル6
入力
6
0 0
-1 0
0 2
3 0
2 0
0 -1
出力
1


原点から全体を監視できるため、1 が出力されます。このサンプルでは頂点の順番は反時計回りではないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。