東京大学プログラミングコンテスト2014

H - 回すだけ


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

背景

この問題は凸多角形を回すだけです。がんばってください。

課題

この問題はリアクティブ形式の問題である。つまり、あなたは応答プログラムの出力を利用して解を求める必要がある。

y 軸正の方向を上、x 軸正の方向を右とする xy 平面上に、1 つの頂点が原点にあり、それ以外の頂点は y 座標が 0 未満の格子点上に存在する凸多角形がある。 この凸多角形の頂点数は 10 以下、頂点の座標は絶対値が 1,000 以下、内角は 170 度以下である。 あなたのプログラムは応答プログラムに対して、原点を中心に指定された角度だけ反時計回りに回転した凸多角形の頂点のうち最も大きな y 座標を尋ねることができる。 この質問を 1,000 回以内の任意の回数だけ用いて凸多角形のもとの座標を求めよ。

配点

300

入出力

あなたのプログラムは凸多角形をある角度 x (度数法による値)だけ反時計回りに回転させた時の頂点のうち最も大きな y 座標 y_{max} を尋ねることができる。 例えば、C/C++ で 12.3 度反時計回りに回転した時の y_{max} を質問するには、まず次のようにする。

printf("? 12.3\n"); fflush(stdout);
そして、次に、
double ymax; scanf("%lf", &ymax);
とすると変数 ymaxy_{max} の値が入る。このとき y_{max} には小数第 10 位の値までがあなたのプログラムに渡される。

凸多角形の座標を出力するときは、次のフォーマットにしたがって行う。

! n
! x_1 y_1
…
! x_n y_n

1行目には ‘!’ (感嘆符) と半角スペース 1 つに続き、凸多角形の頂点数 n を出力する。 2行目からn+1行目には ‘!’ (感嘆符) と半角スペース 1 つに続き凸多角形の頂点の座標を整数値で原点から順に反時計回りに出力する。あなたのプログラムは凸多角形の座標を終了したあと、ただちに終了しなければならない。

以下のときのジャッジ結果は不定である。

C/C++ 以外での入出力方法については、過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径 ) を参考にしてもよい。

入出力例

説明 プログラムの出力 プログラムへの入力
180度回転させた時の y_{max} を尋ねている。 ? 180
質問の答えが返されている。 1
凸多角形の頂点数を答えている。 ! 3
1つめの頂点の座標(原点)を答えている。 ! 0 0
2つめの頂点の座標を答えている。 ! -1 -1
3つめの頂点の座標を答えている。 ! 1 -1

Submit提出する