蓝桥杯2093: 蓝桥杯算法训练VIP-Tiling the Plane题解

旧巴黎 算法基础篇 46 0
想要检验自己的编程水平?来试试全网最全C++题库,让您在挑战中不断进步。
对于一个多边形,如果可以通过它本身复制多次来不重不漏地覆盖一个无限的二维平面,我们就称这个多边形能铺满平面,图1展示了一个L型的多边形,图2展示了它如何不重不漏地铺满平面,你需要写一个程序来判断给出的多边形是否能铺满平面。

对于一个多边形,如果可以通过它本身复制多次来不重不漏地覆盖一个无限的二维平面,我们就称这个多边形能铺满平面。图1展示了一个L型的多边形,图2展示了它如何不重不漏地铺满平面。你需要写一个程序来判断给出的多边形是否能铺满平面。 每组测试数据由一个闭合的多边形组成,这个多边形所有的角均为直角,每条边的长度均为单位长度的整数倍。你可以随意地复制这个多边形,也可以在平面上随意移动它们,但不能旋转或翻转任意一个多边形。 以下是一些可能有用的信息: 只有两种本质不同的铺满平面的情况:使用正四边形铺满平面(棋盘覆盖),或使用正六边形铺满平面(蜂巢覆盖)。一个多边形当且仅当满足以下两个条件中至少一个时可以铺满平面: 1. 在多边形边界上顺次存在四个点A,B,C,D(不一定要是多边形的顶点),使得A到B的边界与D到C的边界重合,B到C的边界与A到D的边界重合。这表明这个多边形可以用棋盘覆盖的方式铺满平面。 2. 在多边形边界上顺次存在六个点A,B,C,D,E,F(不一定要是多边形的顶点),使得A到B的边界与E到D的边界重合,B到C的边界与F到E的边界重合,C到D的边界与A到F的边界重合。这表明这个多边形可以用蜂巢覆盖的方式铺满平面。

蓝桥杯2093: 蓝桥杯算法训练VIP-Tiling the Plane题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
成为编程大师,不再是梦想!全网最全C++题库,助您开启编程新篇章。

标签: 蓝桥杯2093: 蓝桥杯算法训练VIP-Tiling the Plane题解