← 返回题目列表

AtCoder · utpc2014_h

H. 转动即可

中文机器翻译题面 查看原题

問題

背景

这道题只是旋转凸多边形而已。请加油。

課題

这道题是反应式形式的问题。也就是说,你需要利用应答程序的输出来求解。

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);
表示变量 ymax 至 该值是 y_{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
正在回答第一个顶点的坐标(原点)。 ! 0 0
正在回答第二个顶点的坐标。 ! -1 -1
正在回答第三个顶点的坐标。 ! 1 -1