No.3154 convex polygon judge
タグ : / 解いたユーザー数 77
作問者 :


問題文
$2$ 次元座標平面上の相異なる位置に $N$ 個の点があり、 $i$ $(1 \leq i \leq N)$ 番目の点の座標は $(X_i,Y_i)$ です。
はじめ、 $1$ 本も線分は引かれていません。適切に相異なる $2$ 点を選び線分で結ぶ操作を $N$ 回繰り返すことで、狭義凸 $N$ 角形を作ることが出来るか判定してください。
狭義凸 $N$ 角形とは
どの内角も $180$ 度未満であるような $N$ 角形 $(3 \leq N)$ のことを、狭義凸 $N$ 角形といいます。内角が $180$ 度の頂点がある場合に注意してください。制約
- $3 \leq N \leq 2 \times 10^{5}$
- $0 \leq X_i,Y_i \leq 10^9 (1 \leq i \leq N)$
- $i \neq j \Rightarrow (X_i,Y_i) \neq (X_j,Y_j)$
- 入力はすべて整数
入力
$N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$
出力
狭義凸 $N$ 角形を作ることが出来るなら Yes
を、そうでなければ No
を出力してください。
サンプル
サンプル1
入力
4 0 0 4 0 3 3 0 4
出力
Yes
点 $1$ と点 $4$ 、点 $4$ と点 $3$ 、点 $3$ と点 $2$ 、点 $2$ と点 $1$ 、を結ぶと、凸 $4$ 角形ができます。したがって Yes
を出力してください。
サンプル2
入力
4 0 0 1 1 4 0 0 4
出力
No
どのように線を結んでも凸 $4$ 角形は出来ません。したがって No
を出力してください。
サンプル3
入力
5 0 0 2 0 4 0 3 3 0 4
出力
No
点 $1$ と点 $2$ 、点 $2$ と点 $3$ 、点 $3$ と点 $4$ 、点 $4$ と点 $5$ 、点 $5$ と点 $1$、を結ぶと、凸多角形ができます。しかし、点 $1$ と点 $2$ および点 $3$ が一直線上に並んでおり、点 $2$ が $5$ 角形の頂点とは言えないので、これは凸 $4$ 角形になります。
この他、どのように線分を引いても凸 $5$ 角形は出来ません。したがって No
を出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。