問題一覧 > 通常問題

No.2602 Real Collider

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : 👑 amentorimaruamentorimaru / テスター : cleanttedcleantted 👑 seekworserseekworser
2 ProblemId : 10282 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-01-08 13:25:38

問題文

仮想空間を楽しむにあたって、現実世界の物体との衝突を避けることは必須です。


リアルワーニュくんは現在十分に広い二次元平面上の部屋にいて、 (XA,YA),(XB,YB),(XC,YC)(X_A,Y_A),(X_B,Y_B),(X_C,Y_C) の三つの異なる座標を決定するとその三点を含む最小半径の円がプレイエリアとして定義されます。

現在部屋には QQ 個の荷物が置いてあり、 それぞれ (Xi,Yi)(X_i,Y_i) の座標に置いてあります。

プレイエリアの中の荷物は片づける必要がありますので、片づける必要があるか否かを YesNoで答えてください。

なお荷物・プレイエリアの定義の座標ともに円周上も円の中に含まれていると判定されるものとします。

入力

QQ
XA YA XB YB XC YC X_A\ Y_A\ X_B\ Y_B\ X_C\ Y_C\ 
X1 Y1X_1\ Y_1
X2 Y2X_2\ Y_2
\vdots
XQ YQX_Q\ Y_Q

  • 入力は全て整数
  • 1Q2×1051\le Q \le 2\times 10^5
  • XA,XB,XC,YA,YB,YC,Xi,Yi104|X_A|,|X_B|,|X_C|,|Y_A|,|Y_B|,|Y_C|,|X_i|,|Y_i|\le 10^4
  • (XA,YA),(XB,YB),(XC,YC)(X_A,Y_A),(X_B,Y_B),(X_C,Y_C) は全て異なる

出力

QQ 個の各荷物ごとに片づける必要があるならばYesを、そうでないならばNoで改行区切りで答えよ

サンプル

サンプル1
入力
5
1 0 -1 0 0 2
0 1
0 2
0 3
2 2
0 -1
出力
Yes
Yes
No
No
No

下記のような図で配置されます。 (XA,YA),(XB,YB),(XC,YC)(X_A,Y_A),(X_B,Y_B),(X_C,Y_C) が赤色の点になり、青色の線がプレイエリアになり、荷物の場所が緑色の点になります。

(0,1)(0,1) はこの円の中に入っている為Yesを出力します

(0,2)(0,2) は円周上もこの円の中に入っている為Yesを出力します

(2,2)(2,2) はこの円の中に入っていない為Noを出力します

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

プレイエリアは三点を含む最小半径の円であることにご注意ください。

サンプル3
入力
5
0 0 6 0 0 8
6 8
7 7
7 1
-1 7
-1 1
出力
Yes
Yes
Yes
Yes
Yes

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