Lát kín mặt phẳng
Đề bài
Mô tả
Một đa giác được gọi là "lát kín mặt phẳng" nếu có thể ghép một tập hợp các bản sao giống hệt nhau của đa giác đó để phủ kín một mặt phẳng hai chiều vô hạn mà không có khe hở hay chồng lấn. Chẳng hạn Hình 1 là một đa giác hình chữ L, và Hình 2 cho thấy một phần mặt phẳng được lát bằng các bản sao của đa giác đó. Bạn cần viết chương trình xác định một đa giác cho trước có lát kín được mặt phẳng hay không.

Hình 1 (trái): một đa giác thử trên lưới ô vuông đơn vị. Hình 2 (phải): một phần mặt phẳng được lát bằng đa giác đó.
Mỗi bộ dữ liệu là một đa giác khép kín, trong đó mọi đỉnh đều là góc vuông và độ dài mỗi cạnh là bội nguyên của một đơn vị độ dài. Bạn được dùng bao nhiêu bản sao của đa giác tuỳ ý và được di chuyển chúng trên mặt phẳng, nhưng không được quay hay lật đối xứng bất kỳ bản sao nào.
Thông tin sau có thể hữu ích: người ta đã biết rằng chỉ có hai cách lát mặt phẳng khác nhau về bản chất, đó là cách lát bằng hình vuông đều (kiểu bàn cờ) và cách lát bằng lục giác đều (kiểu tổ ong). Do đó một đa giác lát kín được mặt phẳng khi và chỉ khi nó thoả mãn một trong hai điều kiện sau:
- Có các điểm nằm theo thứ tự trên biên đa giác (các điểm này không nhất thiết là đỉnh của đa giác) sao cho phần biên từ tới và phần biên từ tới bằng nhau, đồng thời phần biên từ tới và phần biên từ tới bằng nhau. Trường hợp này dẫn tới một cách lát tương đương với cách lát bằng hình vuông.
- Có các điểm nằm theo thứ tự trên biên đa giác sao cho các cặp phần biên và , và , và bằng nhau. Trường hợp này dẫn tới một cách lát tương đương với cách lát bằng lục giác.
Ở đây hai phần biên bằng nhau nghĩa là phần này trùng khít với phần kia sau một phép tịnh tiến (đi từ điểm đầu tới điểm cuối của mỗi phần theo đúng thứ tự tên điểm).
Dữ liệu vào
Dữ liệu gồm mô tả của nhiều đa giác, mỗi mô tả nằm trên một dòng. Mỗi mô tả bắt đầu bằng số nguyên là số cạnh của đa giác. Tiếp theo là mô tả của đoạn thẳng, theo thứ tự tạo thành một vòng đi ngược chiều kim đồng hồ quanh chu vi đa giác. Mỗi đoạn thẳng được mô tả bằng một chữ cái và một số nguyên. Chữ cái là N, E, S hoặc W, cho biết hướng của đoạn thẳng lần lượt là Bắc, Đông, Nam hoặc Tây. Số nguyên là độ dài của đoạn thẳng tính theo đơn vị độ dài. Đa giác được mô tả không tự chạm và không tự cắt.
Dữ liệu kết thúc bằng một dòng chứa số .
Dữ liệu ra
Với mỗi đa giác, in một dòng gồm số thứ tự của đa giác trong dữ liệu, sau đó là từ Possible nếu có thể lát kín mặt phẳng bằng đa giác đó, hoặc Impossible nếu không. Theo đúng định dạng trong ví dụ.
Ràng buộc
- .
- Độ dài mỗi cạnh là số nguyên từ đến ; hai cạnh liên tiếp (kể cả cạnh cuối và cạnh đầu) luôn vuông góc với nhau.
- Mỗi file có không quá đa giác, và tổng độ dài các cạnh của mọi đa giác trong file không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 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 |
Đặt đỉnh đầu tiên tại . Đa giác 1 là hình chữ L của Hình 1: chọn , , , , , thì và cùng là một bước sang tây, và cùng là một bước xuống nam, và cùng là bước xuống nam rồi bước sang đông. |
| 4 E 3 N 2 W 3 S 2 6 E 2 N 2 W 1 N 1 W 1 S 3 8 E 3 N 2 W 1 S 1 W 1 N 1 W 1 S 2 0 |
Polygon 1: Possible Polygon 2: Possible Polygon 3: Impossible |
Ví dụ tự thêm. Đa giác 1 là hình chữ nhật (điều kiện thứ nhất với là bốn đỉnh). Đa giác 2: đỉnh đầu tại , chọn , , , , , thoả mãn điều kiện thứ hai: và cùng là một bước sang đông, và cùng là bước lên bắc, và cùng là một bước sang tây rồi một bước lên bắc ( và nằm giữa cạnh, không phải đỉnh). Đa giác 3 là hình chữ U, không lát kín được mặt phẳng nếu không quay. |
https://oj.chuyentin.pro/problem/icpcwf05_g
Bình luận