#P18105. Incident in the Bakery

Incident in the Bakery

Incident in the Bakery

给定一个严格凸多边形 CC,顶点 C1,C2,…,CnC_1,C_2,\ldots,C_n 按逆时针顺序给出。请恢复一个同样有 nn 个顶点、严格凸且顶点按逆时针排列的多边形 AA,使下面的操作连续执行两次后得到 CC:

取当前多边形每条边的中点,并按原顺序连接这些中点。

具体来说,第一次操作得到多边形 BB,第二次得到 CC,要求

$$B_i=\frac{A_i+A_{i+1}}2,\qquad C_i=\frac{B_i+B_{i+1}}2.$$

所有下标循环使用,即 An+1=A1A_{n+1}=A_1、Bn+1=B1B_{n+1}=B_1。如果不存在这样的 AA,报告无解。

输入保证:如果存在答案,就一定存在一个合法的 AA,其每个顶点的两个坐标都是4的整数倍,且坐标绝对值不超过 10910^9。 这只是对输入的保证,输出不必使用整数坐标。

输入格式

第一行包含测试用例数 tt,1≤t≤75001\le t\le7500。

每组测试用例的第一行包含 nn,3≤n≤10003\le n\le1000。

接下来 nn 行,每行包含两个整数 xi,yix_i,y_i,表示 CiC_i,满足 ∣xi∣,∣yi∣≤109|x_i|,|y_i|\le10^9。

保证每组输入的 CC 严格凸,顶点按逆时针排列。所有测试用例的 nn 之和不超过 10510^5。

输出格式

每组测试用例:

  • 无解时输出 NO。
  • 有解时先输出 YES,再输出 nn 行,第 ii 行为 AiA_i 的两个坐标。可以输出任意满足要求的方案。

输出坐标可以是实数,但其绝对值不得超过 4⋅1094\cdot10^9。YES 和 NO 不区分大小写。

输出顶点必须构成严格凸、逆时针的多边形,并且对每个 ii 满足

[Ai+1−Ai, Ai+2−Ai+1]>10−7,[A_{i+1}-A_i,\ A_{i+2}-A_{i+1}]>10^{-7},

其中 [u,v]=uxvy−uyvx[u,v]=u_xv_y-u_yv_x,下标取模。

将输出方案进行两次中点操作后,所得第 ii 个点的每个坐标与输入 CiC_i 对应坐标的绝对误差或相对误差不得超过 10−610^{-6}。也就是对输入坐标 cc 和计算结果 vv,要求

∣v−c∣≤10−6max⁡(1,∣c∣).|v-c|\le10^{-6}\max(1,|c|).

样例

3
3
5 4
4 5
3 3
4
3 1
3 3
1 3
1 1
6
0 0
2 0
4 1
3 3
1 4
0 2
YES
0 0
8 4
4 8
YES
0 0.5
4 -0.5
4 4.5
0 3.5
NO

第二组存在不止一种合法方案;第三组不存在合法的原多边形。