問題一覧 > 通常問題

No.3154 convex polygon judge

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 77
作問者 : Cafe1942 / テスター : kazuppa sclara lif4635 kk2a
ProblemId : 12269 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-05-20 21:39:55

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。