#P18105. Incident in the Bakery
Incident in the Bakery
Incident in the Bakery
给定一个严格凸多边形 ,顶点 按逆时针顺序给出。请恢复一个同样有 个顶点、严格凸且顶点按逆时针排列的多边形 ,使下面的操作连续执行两次后得到 :
取当前多边形每条边的中点,并按原顺序连接这些中点。
具体来说,第一次操作得到多边形 ,第二次得到 ,要求
$$B_i=\frac{A_i+A_{i+1}}2,\qquad C_i=\frac{B_i+B_{i+1}}2.$$所有下标循环使用,即 、。如果不存在这样的 ,报告无解。
输入保证:如果存在答案,就一定存在一个合法的 ,其每个顶点的两个坐标都是4的整数倍,且坐标绝对值不超过 。 这只是对输入的保证,输出不必使用整数坐标。
输入格式
第一行包含测试用例数 ,。
每组测试用例的第一行包含 ,。
接下来 行,每行包含两个整数 ,表示 ,满足 。
保证每组输入的 严格凸,顶点按逆时针排列。所有测试用例的 之和不超过 。
输出格式
每组测试用例:
- 无解时输出
NO。 - 有解时先输出
YES,再输出 行,第 行为 的两个坐标。可以输出任意满足要求的方案。
输出坐标可以是实数,但其绝对值不得超过 。YES 和 NO 不区分大小写。
输出顶点必须构成严格凸、逆时针的多边形,并且对每个 满足
其中 ,下标取模。
将输出方案进行两次中点操作后,所得第 个点的每个坐标与输入 对应坐标的绝对误差或相对误差不得超过 。也就是对输入坐标 和计算结果 ,要求
样例
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
第二组存在不止一种合法方案;第三组不存在合法的原多边形。