- C++
三岁的应明澈的剪纸游戏
- 2025-1-14 14:31:17 @
题目描述 三岁的应明澈对剪纸很感兴趣,他总是喜欢把一个矩形的纸片剪成一个又一个的凸多边形。但是,每一次剪完后,他总是怀疑自己弄丢了一些纸片。睿智的他想到了一个方法来检测纸片是否弄丢:他将这些凸多边形拼起来,如果能够拼成一个矩形,他就认为纸片没有弄丢。由于纸片的数量不是很多,这个工作并不难。但是,久而久之,他对这项工作不感兴趣了,所以,他找到了你,希望你能够告诉他,这些凸多边形纸片能不能够拼成矩形。
输入格式 第一行只有一个正整数 n,表示凸多边形的个数。 以下 n 行每一行描述一个凸多边形,格式如下: 第 i+1 行的第一个数 mi 表示凸多边形的点数,接下来有 mi 对实数,一对实数给出了一个点的坐标,这 mi 个顶点按照从任意一个顶点出发的逆时针顺序给出。且所有实数都在 (−103,103) 的范围内,小数点后不超过 8 位。
输出格式 如果不能拼成矩形,输出只有一行 No。 如果能拼成矩形,输出的第一行为 Yes。 接下来的 n 行描述拼法。 如果能够拼成一个 X×Y 的矩形,那么矩形的四个顶点的坐标是 (0,0),(0,Y),(X,Y),(X,0)。这 n 行输出每一个凸多边形的顶点的坐标(拼成矩形后)。按照输入的顺序,即第一个输出的凸多边形对应输入的第一个凸多边形。对于每一个凸多边形,输出也按照输入的顺序,即一个多边形的第一个顶点对应输入的第一个顶点。这样,输出总共有 n 行,第 i 行有 mi 对数。
输入输出样例
输入样例 1
3 4 0 0 4 -1 5 4 0 4 4 0 0 5 -1 8 3 0 3 4 0 0 0 -8 3 -4 4 0
输出样例 1
Yes 0 4 4 3 5 8 0 8 5 8 4 3 8 0 8 8 0 0 8 0 4 3 0 4
说明/提示 样例说明:如下图,左上、右上和左下描述了输入的凸多边形,右下描述了输出的矩形。
注意 由于矩形纸片的两面的颜色不同,所以纸片只能旋转和平移,不能翻转。所以,输出的 mi 个顶点也应该是逆时针顺序的。
数据范围 对于 100% 的数据,1≤n≤8, 3≤mi≤8。
评分说明 两个实数之差的绝对值小于 10−7 时认为两个实数相等。
4 条评论
-
wangkezhen1 LV 6 @ 2025-4-19 11:11:45
aaaa,
-
2025-3-8 20:38:59@
我×
-
2025-1-14 14:36:10@
做对有重赏!!!!!
-
2025-1-14 14:31:57@
哈哈哈
- 1