#P18280. Jigsaw Puzzle
Jigsaw Puzzle
Jigsaw Puzzle
题目描述
有一张大小为 的正方形纸片。至多进行20次如下操作:在这个正方形内部独立、均匀随机地选择两个点,并画出经过这两个点的直线。
随后,沿所有这些直线把纸片切成 块。每块纸片都经过随机旋转(不会翻转)和平移后交给你。请恢复每块纸片在单位正方形内的位置。
下图来自原题:上方为切割前后的正方形,下方为旋转和平移后的各块纸片。

输入格式
第一行一个整数 (),表示纸片的数量。
接下来依次描述每块纸片。每块纸片的描述以一个整数 ()开始,表示它的顶点数。随后 行,每行两个实数 ,表示一个顶点的坐标。坐标满足 ,给出时均有小数点后12位。
每块纸片的顶点均按逆时针顺序给出。输入由题目所述的随机切割、旋转和平移过程产生。
输出格式
按输入中的纸片顺序输出。对于每块纸片,再按输入中该纸片的顶点顺序,依次输出各顶点恢复后的坐标。
每行输出一个顶点的两个坐标,不要输出纸片数量或顶点数量。每个坐标必须满足 。
你可以对每块纸片进行旋转和平移,但不能翻转或改变其形状。如果存在多种将所有纸片放入单位正方形且互不重叠的方法,可以输出任意一种。
根据原比赛的判定说明,裁判会寻找使输出纸片与输入纸片对应的旋转和平移,并检查对应顶点之间的欧氏距离不超过 。
如果任意两块输出多边形的交集面积大于 ,则答案错误。边界接触不算有正面积的重叠。
样例输入
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
数据范围说明
原题只显式给出了 、每块顶点数 、至多20条切割直线及上述坐标范围。由平面直线划分可推出:最多有211块,每块最多24个顶点,所有纸片的顶点总数不超过844。这些是几何过程的推论,不是用其他随机多边形替代原生成过程。