問題一覧 > スコア問題

No.5009 Draw A Convex Polygon

レベル : / 実行時間制限 : 1ケース 2.600秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 88
作問者 : harurunharurun / テスター : yuusanlondonyuusanlondon
2 ProblemId : 8797 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-01 23:47:37

リアクティブ問題と書かれていますが、スペシャルジャッジ問題です。複数の解が存在します。

問題文

$3$ 以上 $10^6$ 以下を満たす好きな整数 $N$ を1つ選び、 $N$ 個の頂点を周上に含む狭義凸 $N$ 角形をxy平面上に構築してください。

ただし、以下の条件をすべて満たす必要があります。

  • 各頂点の座標 $(x_i,y_i)$ は $-10^9≤x_i,y_i≤10^9$ を満たし、ともに整数である。
  • 隣り合う3頂点を順に $p_i,p_j,p_k$ としたとき、点 $p_j$ は点 $p_i$ と点 $p_k$ を結ぶ線分上に存在しない。
  • 任意の異なる2頂点は重ならない。

出力形式に注意してください。

入力

入力はありません。

出力

$N$
$x_1\ y_2$
$\vdots$
$x_N\ y_N$

まず、1行目に選んだ $N$ を出力してください。

次に、頂点を 反時計回りの順に $N$ 行出力してください。

$i+1$ 行目は反時計回り順で $i$ 番目の頂点 $(x_i,y_i)$ を空白区切りで出力してください。

形式通りでない出力の場合、ジャッジの動作は未定義です。正解とならない場合があります。

ジャッジの都合上、空白と改行は区別します。全て空白区切りで1行に出力したなどの場合は不正解となります。

また、最後に必ず改行し、必ずフラッシュしてください。

得点

選んだ $N$ が得点になります。

$3≤N≤10^6$ を満たしていない場合は不正解となります。

注意点

スコア問題は提出間隔を5分空ける必要があります。

yukicoderの仕様上20MBまでしか出力できませんが、リアクティブジャッジにすることで回避しています。

そのため実行時間制限はジャッジにかかる時間も含んでいます。ジャッジは最大で600ミリ秒ほどかかりますので、実質的な実行制限時間は2秒です。

実行時間を測る場合は、オンライン実行をお使いください。他環境と速度が異なる可能性があります。

出力が多いため高速な言語を使用することをお勧めします。

ジャッジの不備で正解となってしまう例を発見した場合は、質問に 「どのようなケースが正解になってしまうか」 をお教えください。(できれば対処法も教えていただけると幸いです)

システムテストはありませんが、ジャッジの不備等によりリジャッジが行われることがあるため、実装方法によっては点数が変動する場合がございます。ご了承ください。

出力例

出力例1
出力
3
0 0
1 0
0 1

得点は3点になります。

出力例2
出力
6
-3 4
-3 1
0 0
3 1
3 4
0 5

反時計回り順であればどの頂点から初めても構いません。この出力をした場合、6点を得ます。

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