問題一覧 > 通常問題

No.2173 Nightcord

レベル : / 実行時間制限 : 1ケース 2.525秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : tko919tko919 / テスター : nok0nok0
4 ProblemId : 8895 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-24 12:38:00

問題文

二次元平面で表される空の相異なる位置に $N$ 個の星があります。
$i(1 \leq i\leq N)$ 番目の星は位置 $(X_i,Y_i)$ にあり、色は $C_i=1$ のとき赤色、 $C_i=2$ のとき青色です。

$N$ 個のうちちょうど $K$ 個の星からなり、赤い星と青い星をともに $1$ つ以上含む集まりを「星座」と呼びます。
また、ある星座に含まれる赤い星と青い星を分断するような直線が存在しないとき、特に「良い星座」と呼びます。
ただし、直線上に星座を構成する星が乗っている場合は分断しているとはみなしません。

良い星座が存在するか判定してください。

入力

$N\ K$
$X_1\ Y_1\ C_1$
$\vdots$
$X_N\ Y_N\ C_N$

  • $3 \leq K \leq N \leq 3000$
  • $0 \leq |X_i|,|Y_i| \leq 10^9\ (1 \leq i \leq N)$
  • $i \neq j$ ならば $(X_i,Y_i) \neq (X_j,Y_j)$
  • $C_i \in \{1,2\}\ (1 \leq i \leq N)$
  • 入力は全て整数

出力

良い星座が存在するときはYes、そうでないときはNoと出力せよ。

サンプル

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


例えば、星 $2,3,4$ からなる星座は直線 $y=\frac{3}{2}$ によって赤い星と青い星に分断されます。

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


良い星座として星 $1,2,3$ からなるものが挙げられます。
星 $1,3,4$ の集まりは全ての星が赤いので星座ではないこと、星 $1,2,3$ からなる星座について直線 $x=0$ は $2$ 色を分断していると認められないことに注意して下さい。

サンプル3
入力
5 4
-8 -31 2
2 10 2
1 -27 1
4 30 2
-8 27 1
出力
Yes

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