UOJ Logo Universal Online Judge

UOJ

#252. 【Rujia Liu's Present 7】Guess the Convex Polygon

附件下载 统计

A 国最近检测到了 B 国内有不正常的辐射,经调查发现,这是因为 B 国正在耗资百亿研制新式武器——连环阵。可是,由于 B 国对此武器的高度保密措施,A 国的间谍甚至无法确定出连环阵的具体位置。不过,A 国的卫星还是可以找出连环阵所在的基地的。我们现在知道该基地是一个边上含有放射性物质的凸多边形。经研究发现,在这个凸多边形所在的平面内,它具有如下性质:

  • 包含坐标原点;
  • 任意两条边不在同一直线上;
  • 没有和 $x$ 轴或 $y$ 轴平行的边;
  • 所有顶点的 $x$ 坐标和 $y$ 坐标都是整数。

现在 A 国可以通过卫星发出无限大的扇形探测波,与该凸多边形所在平面交于一条直线。不过该直线不是与 $x$ 轴平行,就是与 $y$ 轴平行。通过反射信号,我们可以确定该直线与凸多边形的交点个数和所有交点的坐标(如果有的话)。

现在,需要你写一个程序,通过控制卫星发出的探测波来确定这个凸多边形。

交互格式

本题是一道交互式试题,你的程序需要和交互程序通过标准输入输出进行交互。每次向标准输出打印了一行后,请立即刷新缓冲区。

对于每个测试点,交互库首先给出一个整数 $T$ 表示测试数据组数。

对于每组测试数据,你可以进行如下操作与交互库交互:

  1. 输出一行 AskX x0 表示发出一次平行于 $x$ 轴的射线。
    • 交互库会返回一行,第一个整数 $c$ 表示交点个数,接下来 $2c$ 个整数 $a_i,b_i$ 表示交点的纵坐标为 $\frac{a_i}{b_i}$。
  2. 输出一行 AskY y0 表示发出一次平行于 $y$ 轴的射线。
    • 交互库返回的内容同上。
  3. 输出 $n+1$ 行,第一行 Answer n,接下来 $n$ 行每行两个整数 $x_i,y_i$,表示凸包顶点的个数和坐标,注意坐标必须逆时针输出,但是起点可以任意选。
    • 交互库不会返回任何信息,并将结束这组数据的评测。

对于每组测试数据,你至多使用两种询问次数共 $500$ 次。

样例

交互程序输出 选手程序输出
1
AskX -6
1 2 1
AskX -5
2 -5 1 17 5
AskY 2
2 16 1 -6 1
AskY 20
0
Answer 5
8 -9
16 2
-1 9
-6 2
-5 -5

explanation

这只是一个合法的交互过程示例,不代表这个过程可以唯一确定答案。

数据范围与限制

本题只有一个测试点,保证 $1\leq T\leq 100, 3\leq n\leq 20, |x_i|,|y_i|\leq 10000$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

来源

Uva Online Judge,NOI2003,题目作者刘汝佳,李益明。

特别鸣谢:王玉斌, Md. Mahbubul Hasan