問題描述
對于一個多邊形，如果可以通過它本身復制多次來不重不漏地覆寫一個無限的二維平面，我們就稱這個多邊形能鋪滿平面。圖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的邊界重合。這表明這個多邊形可以用蜂巢覆寫的方式鋪滿平面。
輸入格式
輸入包含對多個多邊形的描述，每一行表示一個詢問的多邊形。
每一行以一個整數n開始，表示多邊形的邊數。接下來按逆時針順序描述每一條邊，每一個描述都是一個字母后跟一個數字，字母是“N”、“E”、“S”或“W”，表示線段的方向分別為北、東、南或西，數字表示該線段長度是多少個單位。保證多邊形不與自身連接或相交。
輸入以單獨一行“0”結束。
輸出格式
對于每個多邊形，輸出一行。
首先輸出多邊形的編號，接下來如果該多邊形能鋪滿平面，則輸出“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
資料規模和約定
30%的資料，n ≤ 20，多邊形周長 ≤ 20
100%的資料，n ≤ 50，多邊形周長 ≤ 50，每個測驗資料中不超過50個多邊形。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/50693.html
標籤：基礎類