#P18280. Jigsaw Puzzle

Jigsaw Puzzle

Jigsaw Puzzle

题目描述

有一张大小为 1×11\times1 的正方形纸片。至多进行20次如下操作:在这个正方形内部独立、均匀随机地选择两个点,并画出经过这两个点的直线。

随后,沿所有这些直线把纸片切成 nn 块。每块纸片都经过随机旋转(不会翻转)和平移后交给你。请恢复每块纸片在单位正方形内的位置。

下图来自原题:上方为切割前后的正方形,下方为旋转和平移后的各块纸片。

原题中的切割及打乱后的纸片

输入格式

第一行一个整数 nn(n≥2n\ge2),表示纸片的数量。

接下来依次描述每块纸片。每块纸片的描述以一个整数 mm(m≥3m\ge3)开始,表示它的顶点数。随后 mm 行,每行两个实数 xi,yix_i,y_i,表示一个顶点的坐标。坐标满足 0.0≤xi,yi≤2.00.0\le x_i,y_i\le2.0,给出时均有小数点后12位。

每块纸片的顶点均按逆时针顺序给出。输入由题目所述的随机切割、旋转和平移过程产生。

输出格式

按输入中的纸片顺序输出。对于每块纸片,再按输入中该纸片的顶点顺序,依次输出各顶点恢复后的坐标。

每行输出一个顶点的两个坐标,不要输出纸片数量或顶点数量。每个坐标必须满足 0.0≤xi,yi≤1.00.0\le x_i,y_i\le1.0。

你可以对每块纸片进行旋转和平移,但不能翻转或改变其形状。如果存在多种将所有纸片放入单位正方形且互不重叠的方法,可以输出任意一种。

根据原比赛的判定说明,裁判会寻找使输出纸片与输入纸片对应的旋转和平移,并检查对应顶点之间的欧氏距离不超过 10−610^{-6}。

如果任意两块输出多边形的交集面积大于 10−610^{-6},则答案错误。边界接触不算有正面积的重叠。

样例输入

4
4
0.440405375916 0.778474079786
0.000000000000 0.090337001520
0.469097990019 0.000000000000
0.702887505082 0.689470121906
4
0.222810526978 0.000000000000
0.270828246634 0.522212063829
0.000000000000 0.547114887265
0.021480010612 0.069880870008
4
0.000000000000 0.312825941471
0.358219176380 0.000000000000
0.532830100286 0.122181578260
0.088431750275 0.414089758021
4
0.158867722074 0.061734605990
0.973532298476 0.000000000000
0.853551564066 0.712811281737
0.000000000000 0.569141075980

样例输出

0.277161636 -0.000000000
0.473262431 0.793116645
0.000000000 0.728029248
0.000000000 0.000000000

0.524415047 1.000000000
0.000000000 1.000000000
0.000000000 0.728029248
0.473262431 0.793116645

1.000000000 1.000000000
0.524415047 1.000000000
0.473262431 0.793116645
1.000000000 0.865558433

0.473262431 0.793116645
0.277161636 -0.000000000
1.000000000 -0.000000000
1.000000000 0.865558433

数据范围说明

原题只显式给出了 n≥2n\ge2、每块顶点数 m≥3m\ge3、至多20条切割直线及上述坐标范围。由平面直线划分可推出:最多有211块,每块最多24个顶点,所有纸片的顶点总数不超过844。这些是几何过程的推论,不是用其他随机多边形替代原生成过程。