題目 2093:
藍橋杯算法訓練VIP-Tiling the Plane
時間限制: 2s
內(nèi)存限制: 192MB 提交: 13 解決: 0
題目描述
對于一個多邊形，如果可以通過它本身復(fù)制多次來不重不漏地覆蓋一個無限的二維平面，我們就稱這個多邊形能鋪滿平面。圖1展示了一個L型的多邊形，圖2展示了它如何不重不漏地鋪滿平面。你需要寫一個程序來判斷給出的多邊形是否能鋪滿平面。
每組測試數(shù)據(jù)由一個閉合的多邊形組成，這個多邊形所有的角均為直角，每條邊的長度均為單位長度的整數(shù)倍。你可以隨意地復(fù)制這個多邊形，也可以在平面上隨意移動它們，但不能旋轉(zhuǎn)或翻轉(zhuǎn)任意一個多邊形。
以下是一些可能有用的信息：
只有兩種本質(zhì)不同的鋪滿平面的情況：使用正四邊形鋪滿平面（棋盤覆蓋），或使用正六邊形鋪滿平面（蜂巢覆蓋）。一個多邊形當且僅當滿足以下兩個條件中至少一個時可以鋪滿平面：
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的邊界重合。這表明這個多邊形可以用蜂巢覆蓋的方式鋪滿平面。
每組測試數(shù)據(jù)由一個閉合的多邊形組成，這個多邊形所有的角均為直角，每條邊的長度均為單位長度的整數(shù)倍。你可以隨意地復(fù)制這個多邊形，也可以在平面上隨意移動它們，但不能旋轉(zhuǎn)或翻轉(zhuǎn)任意一個多邊形。
以下是一些可能有用的信息：
只有兩種本質(zhì)不同的鋪滿平面的情況：使用正四邊形鋪滿平面（棋盤覆蓋），或使用正六邊形鋪滿平面（蜂巢覆蓋）。一個多邊形當且僅當滿足以下兩個條件中至少一個時可以鋪滿平面：
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的邊界重合。這表明這個多邊形可以用蜂巢覆蓋的方式鋪滿平面。
輸入格式
輸入包含對多個多邊形的描述，每一行表示一個詢問的多邊形。
每一行以一個整數(shù)n開始，表示多邊形的邊數(shù)。接下來按逆時針順序描述每一條邊，每一個描述都是一個字母后跟一個數(shù)字，字母是“N”、“E”、“S”或“W”，表示線段的方向分別為北、東、南或西，數(shù)字表示該線段長度是多少個單位。保證多邊形不與自身連接或相交。
每一行以一個整數(shù)n開始，表示多邊形的邊數(shù)。接下來按逆時針順序描述每一條邊，每一個描述都是一個字母后跟一個數(shù)字，字母是“N”、“E”、“S”或“W”，表示線段的方向分別為北、東、南或西，數(shù)字表示該線段長度是多少個單位。保證多邊形不與自身連接或相交。
輸入以單獨一行“0”結(jié)束。
30%的數(shù)據(jù)，n ≤ 20，多邊形周長 ≤ 20
100%的數(shù)據(jù)，n ≤ 50，多邊形周長 ≤ 50，每個測試數(shù)據(jù)中不超過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