题目 2093:
蓝桥杯算法训练VIP-Tiling the Plane
时间限制: 3s
内存限制: 192MB 提交: 11 解决: 0
题目描述
对于一个多边形，如果可以通过它本身复制多次来不重不漏地覆盖一个无限的二维平面，我们就称这个多边形能铺满平面。图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的边界重合。这表明这个多边形可以用蜂巢覆盖的方式铺满平面。
每组测试数据由一个闭合的多边形组成，这个多边形所有的角均为直角，每条边的长度均为单位长度的整数倍。你可以随意地复制这个多边形，也可以在平面上随意移动它们，但不能旋转或翻转任意一个多边形。
以下是一些可能有用的信息：
只有两种本质不同的铺满平面的情况：使用正四边形铺满平面（棋盘覆盖），或使用正六边形铺满平面（蜂巢覆盖）。一个多边形当且仅当满足以下两个条件中至少一个时可以铺满平面：
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的边界重合。这表明这个多边形可以用蜂巢覆盖的方式铺满平面。
输入格式
输入包含对多个多边形的描述，每一行表示一个询问的多边形。
每一行以一个整数n开始，表示多边形的边数。接下来按逆时针顺序描述每一条边，每一个描述都是一个字母后跟一个数字，字母是“N”、“E”、“S”或“W”，表示线段的方向分别为北、东、南或西，数字表示该线段长度是多少个单位。保证多边形不与自身连接或相交。
每一行以一个整数n开始，表示多边形的边数。接下来按逆时针顺序描述每一条边，每一个描述都是一个字母后跟一个数字，字母是“N”、“E”、“S”或“W”，表示线段的方向分别为北、东、南或西，数字表示该线段长度是多少个单位。保证多边形不与自身连接或相交。
输入以单独一行“0”结束。
30%的数据，n ≤ 20，多边形周长 ≤ 20
100%的数据，n ≤ 50，多边形周长 ≤ 50，每个测试数据中不超过50个多边形。
输出格式
对于每个多边形，输出一行。
首先输出多边形的编号，接下来如果该多边形能铺满平面，则输出“Possible”，如果该多边形不能铺满平面，则输出“Impossible”。具体见样例输出的格式。
首先输出多边形的编号，接下来如果该多边形能铺满平面，则输出“Possible”，如果该多边形不能铺满平面，则输出“Impossible”。具体见样例输出的格式。
样例输入
6 N 3 W 1 S 4 E 4 N 1 W 3 8 E 5 N 1 W 3 N 3 E 2 N 1 W 4 S 5 0
样例输出
Polygon 1: Possible Polygon 2: Impossible